QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#367363#8513. Insects, Mathematics, Accuracy, and Efficiencyucup-team266#WA 4ms16500kbC++146.4kb2024-03-25 21:40:172024-03-25 21:40:18

Judging History

你现在查看的是最新测评结果

  • [2024-03-25 21:40:18]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:16500kb
  • [2024-03-25 21:40:17]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef array<int, 3> ai3;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const int Mod = 1e9 + 7;
inline int sign(int a){ return (a&1) ? (Mod-1) : 1; }
inline void uadd(int &a, int b){ a += b-Mod; a += (a>>31) & Mod; }
inline void usub(int &a, int b){ a -= b, a += (a>>31) & Mod; }
inline void umul(int &a, int b){ a = (int)(1ll * a * b % Mod); }
inline int add(int a, int b){ a += b-Mod; a += (a>>31) & Mod; return a; }
inline int sub(int a, int b){ a -= b, a += (a>>31) & Mod; return a; }
inline int mul(int a, int b){ a = (int)(1ll * a * b % Mod); return a; }
int qpow(int b, ll p){ int ret = 1; while(p){ if(p&1) umul(ret, b); umul(b, b), p >>= 1; } return ret; }
const int fN = 100;
int fact[fN], invfact[fN], pw2[fN], invpw2[fN], inv[fN];
void initfact(int n){
	pw2[0] = 1; for(int i = 1; i <= n; ++i) pw2[i] = mul(pw2[i-1], 2);
	invpw2[0] = 1; for(int i = 1; i <= n; ++i) invpw2[i] = mul(invpw2[i-1], (Mod+1) / 2);
	fact[0] = 1; for(int i = 1; i <= n; ++i) fact[i] = mul(fact[i-1], i);
	invfact[n] = qpow(fact[n], Mod-2); for(int i = n; i > 0; --i) invfact[i-1] = mul(invfact[i], i);
	for(int i = 1; i <= n; ++i) inv[i] = mul(invfact[i], fact[i-1]);
}
int binom(int n, int m){ return (m < 0 || m > n) ? 0 : mul(fact[n], mul(invfact[m], invfact[n-m])); }
const ld pi = acos(-1);
inline void chmax(int &a, int b){ (b>a) ? (a=b) : 0; }
inline void chmin(int &a, int b){ (b<a) ? (a=b) : 0; }

const ld eps = 1e-8;
inline int sign(ld x){ return (x > eps ? +1 : (x < -eps ? -1 : 0)); }
struct vec{
	ld x, y;
	vec(){ x = y = 0; }
	vec(ld _x, ld _y){ x = _x, y = _y; }
};
inline bool operator <(vec lh, vec rh){ return (sign(lh.x - rh.x) ? (lh.x < rh.x) : (sign(lh.y - rh.y) < 0)); } // 比大小,先比 x 后比 y
inline ld len(vec v){ return sqrtl(v.x*v.x + v.y*v.y); } // 模长
inline ld len2(vec v){ return v.x*v.x + v.y*v.y; } // 模长^2
inline vec operator +(vec lh, vec rh){ return vec(lh.x + rh.x, lh.y + rh.y); } // 向量加
inline vec operator -(vec lh, vec rh){ return vec(lh.x - rh.x, lh.y - rh.y); } // 向量减
inline vec operator *(vec lh, ld rh){ return vec(lh.x * rh, lh.y * rh); }
inline vec operator *(ld lh, vec rh){ return vec(lh * rh.x, lh * rh.y); }
inline ld Dot(vec lh, vec rh){ return lh.x * rh.x + lh.y * rh.y; } // 向量点乘
inline ld Cross(vec lh, vec rh){ return lh.x * rh.y - lh.y * rh.x; } // 向量叉乘
inline vec Norm(vec v){ return vec(v.y, -v.x); } // 法向量
struct Line{
	vec A, B;
	Line(vec _A = vec(), vec _B = vec()){ A = _A, B = _B; }
};
inline ld dis_p_l(vec P, Line l){ // 点到直线的距离。叉积除以底。
	return fabs(Cross(P - l.A, l.B - l.A)) / len(l.B - l.A);
}
inline bool inrec(vec P, Line l){ // 判断点是否在线段的四至矩形内(含边界)。
	return sign(P.x - min(l.A.x, l.B.x)) >= 0 && sign(P.x - max(l.A.x, l.B.x)) <= 0
		&& sign(P.y - min(l.A.y, l.B.y)) >= 0 && sign(P.y - max(l.A.y, l.B.y)) <= 0;
}
inline bool isinter(Line a, Line b){ // 判断线段相交(不含端点,不含直线重合,大概)。跨立实验(不含直线重合不需要快速排斥罢(?))
	return (sign(Cross(a.A - b.A, b.B - b.A) * Cross(a.B - b.A, b.B - b.A)) < 0 && sign(Cross(b.A - a.A, a.B - a.A) * Cross(b.B - a.A, a.B - a.A)) < 0);
}

int n; ld R;
vec a[100100];
int h[100100], hp = 0;
void Andrew(){ // 求凸包。
	sort(a, a+n);
	rep(i, n){
		while(hp > 1 && sign(Cross(a[h[hp-1]] - a[h[hp-2]], a[i] - a[h[hp-1]])) <= 0) --hp;
		h[hp++] = i;
	}
	int st = hp-1;
	for(int i = n-2; i >= 0; --i){
		while(hp > st + 1 && sign(Cross(a[h[hp-1]] - a[h[hp-2]], a[i] - a[h[hp-1]])) <= 0) --hp;
		h[hp++] = i;
	}
	--hp;
	static vec tmp[100100];
	rep(i, hp) tmp[i] = a[h[i]];
	rep(i, hp) a[i] = tmp[i];
	n = hp;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> R;
	//R += eps;
	rep(i, n) cin >> a[i].x >> a[i].y;
	Andrew();

	if(n <= 1) return cout << "0.0\n", 0;

	static vec to[100100], fr[100100];
	static ld to_a[100100], fr_a[100100];
	rep(i, n){
		vec A = a[(i+1) % n], B = a[i];
		ld t0, t1;
		{
			ld va = len2(A - B), vb = 2. * ((A.x - B.x) * B.x + (A.y - B.y) * B.y), vc = (B.x * B.x + B.y * B.y - R * R);
			ld lam = vb * vb - 4. * va * vc;
			t0 = (-vb + sqrtl(lam)) / (2. * va);
			t1 = (-vb - sqrtl(lam)) / (2. * va);
		}
		to[i] = (t0 * A + (1. - t0) * B); to_a[i] = atan2(to[i].y, to[i].x);
		fr[i] = (t1 * A + (1. - t1) * B); fr_a[i] = atan2(fr[i].y, fr[i].x);
	}

	//rep(i, n) cout << a[i].x << " " << a[i].y << "\n";
	//cout << "------\n";
	//rep(i, n) cout << to[i].x << " " << to[i].y << "   " << fr[i].x << " " << fr[i].y << "\n";
	
	int st0 = 0, st1 = 0;
	rep(i, n) if(to_a[i] < to_a[st0]) st0 = i;
	rep(i, n) if(fr_a[i] < fr_a[st1]) st1 = i;
	int p0 = st0, p1 = st1;
	ld lb = -100; vec lbv;
	rep(i, n) if(to_a[i] > lb) lb = to_a[i], lbv = to[i];
	rep(i, n) if(fr_a[i] > lb) lb = fr_a[i], lbv = fr[i];
	ld ans = -1, cur = 0;
	for(int i = p1; i != p0; i = (i+1) % n){
		//cout << i << " " << p0 << ": " << (a[(i+1) % n] - a[i]).x << " " << (a[(i+1) % n] - a[i]).y << "  *  " << (a[p0] - a[i]).x << " " << (a[p0] - a[i]).y << "\n";
		cur += Cross(a[(i+1) % n] - a[i], a[p0] - a[i]) * 0.5;
	}
	while(1){
		ld ub; vec ubv;
		if(to_a[p0] < fr_a[p1])
			ub = to_a[p0], ubv = to[p0];
		else 
			ub = fr_a[p1], ubv = fr[p1];
		//cout << p0 << " " << p1 << "  " << lb << " " << ub << "   + " << cur << "\n";
		if(p0 != p1){
			vec mx = Norm(a[p1] - a[p0]);
			//cout << mx.x << " " << mx.y << "\n";
			mx = mx * (R / len(mx));
			//cout << mx.x << " " << mx.y << "\n";
			ld mx_a = atan2(mx.y, mx.x);
			if(sign(ub - lb) < 0){
				lb -= 2. * pi, mx_a -= 2. * pi;
			}
			vec T = ((sign(mx_a - lb) >= 0 && sign(mx_a - ub) <= 0) ? mx : ((mx_a <= lb) ? lbv : ubv));
			//cout << T.x << " " << T.y << "\n";
			ans = max(ans, cur + Cross(a[p1] - T, a[p0] - T) * 0.5);
		}
		if(to_a[p0] < fr_a[p1]){
			int np0 = (p0 + 1) % n;
			cur += Cross(a[p1] - a[np0], a[p0] - a[np0]) * 0.5;
			p0 = np0;
			if(p0 == st0) break;
		} else {
			int np1 = (p1 + 1) % n;
			cur -= Cross(a[np1] - a[p1], a[p0] - a[p1]) * 0.5;
			p1 = np1;
			if(p1 == st1) break;
		}
		lb = ub, lbv = ubv;
	}

	cout << fixed << setprecision(12) << ans << "\n";

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 16424kb

input:

4 1000
-1000 0
0 0
1000 0
0 -1000

output:

2000000.000000000000

result:

ok found '2000000.000000000', expected '2000000.000000000', error '0.000000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 16396kb

input:

2 100
17 7
19 90

output:

4849.704644437564

result:

ok found '4849.704644438', expected '4849.704644438', error '0.000000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 10036kb

input:

1 100
13 37

output:

0.0

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #4:

score: 0
Accepted
time: 0ms
memory: 16424kb

input:

4 1000
-800 600
800 600
-800 -600
800 -600

output:

2240000.000000000000

result:

ok found '2240000.000000000', expected '2240000.000000000', error '0.000000000'

Test #5:

score: 0
Accepted
time: 0ms
memory: 16500kb

input:

3 1000
200 400
-600 -400
400 -800

output:

1045685.424949238020

result:

ok found '1045685.424949238', expected '1045685.424949238', error '0.000000000'

Test #6:

score: -100
Wrong Answer
time: 4ms
memory: 16248kb

input:

4 1000
200 -600
600 -400
800 -600
0 -800

output:

700000.000000000000

result:

wrong answer 1st numbers differ - expected: '732310.5625618', found: '700000.0000000', error = '0.0441214'