QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#367363 | #8513. Insects, Mathematics, Accuracy, and Efficiency | ucup-team266# | WA | 4ms | 16500kb | C++14 | 6.4kb | 2024-03-25 21:40:17 | 2024-03-25 21:40:18 |
Judging History
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;
}
详细
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'