QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#367350 | #8513. Insects, Mathematics, Accuracy, and Efficiency | ucup-team266# | WA | 1ms | 6068kb | C++14 | 6.3kb | 2024-03-25 21:26:16 | 2024-03-25 21:26:16 |
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 double 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 double eps = 1e-8;
inline int sign(double x){ return (x > eps ? +1 : (x < -eps ? -1 : 0)); }
struct vec{
double x, y;
vec(){ x = y = 0; }
vec(double _x, double _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 double len(vec v){ return sqrt(v.x*v.x + v.y*v.y); } // 模长
inline double 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, double rh){ return vec(lh.x * rh, lh.y * rh); }
inline vec operator *(double lh, vec rh){ return vec(lh * rh.x, lh * rh.y); }
inline double Dot(vec lh, vec rh){ return lh.x * rh.x + lh.y * rh.y; } // 向量点乘
inline double 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 double 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; double 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;
rep(i, hp) a[i] = a[h[i]];
n = hp;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> R;
rep(i, n) cin >> a[i].x >> a[i].y;
Andrew();
if(n <= 1) return cout << "0.0\n", 0;
static vec to[10010], fr[10010];
static double to_a[10010], fr_a[10010];
rep(i, n){
vec A = a[(i+1) % n], B = a[i];
double t0, t1;
{
double 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);
double lam = vb * vb - 4. * va * vc;
t0 = (-vb + sqrt(lam)) / (2. * va);
t1 = (-vb - sqrt(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;
double 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];
double ans = -1, cur = 0;
for(int i = p1; i != p0; i = (i+1) % n){
cur += Cross(a[(i+1) % n] - a[i], a[p0] - a[i]) * 0.5;
}
while(1){
double 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";
double 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: 1ms
memory: 6040kb
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: 6020kb
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: 1ms
memory: 5268kb
input:
1 100 13 37
output:
0.0
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 6068kb
input:
4 1000 -800 600 800 600 -800 -600 800 -600
output:
1280000.000000000000
result:
wrong answer 1st numbers differ - expected: '2240000.0000000', found: '1280000.0000000', error = '0.4285714'