QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#280803 | #7783. Military Maneuver | ucup-team266# | TL | 0ms | 3784kb | C++20 | 4.5kb | 2023-12-09 17:57:07 | 2023-12-09 17:57:08 |
Judging History
answer
//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ld double
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
#define head l
#define tail r
void die(string S){puts(S.c_str());exit(0);}
const ld eps=1e-12;
int x[2020],y[2020];
struct Point
{
ld x,y;
Point(){}
Point(ld _x,ld _y):x(_x),y(_y){}
friend Point operator -(Point a,Point b)
{
return Point{a.x-b.x,a.y-b.y};
}
friend ld operator *(Point a,Point b)
{
return a.x*b.y-a.y*b.x;
}
friend bool operator ==(Point a,Point b)
{
return fabs(a.x-b.x)<eps&&fabs(a.y-b.y)<eps;
}
friend Point operator *(ld a,Point b)
{
return Point{a*b.x,a*b.y};
}
friend ld sqrd(Point x)
{
return x.x*x.x+x.y*x.y;
}
friend ld sqrd(Point a,Point b)
{
return sqrd(a-b);
}
friend ld dist(Point a,Point b)
{
return sqrtl(sqrd(a,b));
}
};
ld atan2_kevin(Point p){return atan2l(p.y,p.x);}
struct Line
{
Point a,b;
Line(){}
Line(Point _a,Point _b):a(_a),b(_b){}
friend bool operator <(Line a,Line b)
{
ld t1=atan2_kevin(a.b-a.a);
ld t2=atan2_kevin(b.b-b.a);
if(fabs(t1-t2)>eps) return t1<t2;
return (b.a-a.a)*(b.b-a.a)>eps;
}
friend bool operator ==(Line a,Line b)
{
return a.a==b.a&&a.b==b.b;
}
};
Point its(Line a,Line b)
{
ld v1=(b.b-b.a)*(a.b-b.b);
ld v2=(b.b-b.a)*(a.b-a.a);
ld T=v1/v2;
return a.b-T*(a.b-a.a);
}
Point sw(Point x)
{
return Point(x.y,-x.x);
}
Point cvh[2020];
Line lns[2020];
int head,tail;
ld calc2(Point a,Point b)
{
ld S2=b*a;
ld lsq=sqrd(a,b);
ld l=sqrtl(lsq);
ld retx=S2/lsq*S2/4;
ld rety1=lsq/12;
Point perp=its(Line(a,b),Line(Point(0,0),sw(b-a)));
ld la=dist(perp,a);
ld lb=dist(perp,b);
if(fabs(la+lb-l)<eps)
la=-la;
ld rety2=la*lb/4;
// cerr<<"("<<a.x<<","<<a.y<<")"<<endl;
// cerr<<"("<<b.x<<","<<b.y<<")"<<endl;
// cerr<<S2<<" "<<l<<" "<<retx<<" "<<rety1<<" "<<rety2<<endl;
return (retx+rety1+rety2)*S2;
}
ld calc(vector<Line> vec,Point center)
{
srt(vec);
head=tail=0;
int n=sz(vec);
uni(vec);
// for(auto v:vec)
// cerr<<"("<<v.a.x<<","<<v.a.y<<"),("<<v.b.x<<","<<v.b.y<<")"<<endl;
for(int i=0;i<n;i++)
{
while(tail-head>1&&(vec[i].b-cvh[r])*(vec[i].a-cvh[r])>-eps)
r--;
while(tail-head>1&&(vec[i].b-cvh[l+2])*(vec[i].a-cvh[l+2])>-eps)
l++;
lns[++r]=vec[i];
if(tail-head>1) cvh[r]=its(lns[r],lns[r-1]);
}
while(tail-head>1&&(lns[l+1].b-cvh[r])*(lns[l+1].a-cvh[r])>-eps)
r--;
if(tail-head<3) return 0;
cvh[l+1]=its(lns[l+1],lns[r]);
// for(int i=l+1;i<=r;i++)
// cerr<<cvh[i].x<<" "<<cvh[i].y<<endl;
cvh[r+1]=cvh[l+1];
ld ret=0.0;
for(int i=l+1;i<=r;i++)
ret+=calc2(cvh[i+1]-center,cvh[i]-center);
return ret;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
x1*=2;
y1*=2;
x2*=2;
y2*=2;
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>x[i]>>y[i];
x[i]*=2;
y[i]*=2;
}
ld ans=0.0;
for(int i=1;i<=n;i++) // expected dist squared when Pi is nearest
{
vector<Line> vec;
vec.pb(Point(x1,y2),Point(x1,y1));
vec.pb(Point(x2,y2),Point(x1,y2));
vec.pb(Point(x2,y1),Point(x2,y2));
vec.pb(Point(x1,y1),Point(x2,y1));
for(int j=1;j<=n;j++) if(j!=i)
{
int mx=(x[i]+x[j])/2,my=(y[i]+y[j])/2;
int dx=(x[j]-x[i])/2,dy=(y[j]-y[i])/2;
vec.pb(Point(mx,my),Point(mx-dy,my+dx));
}
ans-=calc(vec,Point(x[i],y[i]));
// cerr<<ans<<endl;
}
for(int i=1;i<=n;i++) // expected dist squared when Pi is farthest
{
vector<Line> vec;
vec.pb(Point(x1,y2),Point(x1,y1));
vec.pb(Point(x2,y2),Point(x1,y2));
vec.pb(Point(x2,y1),Point(x2,y2));
vec.pb(Point(x1,y1),Point(x2,y1));
for(int j=1;j<=n;j++) if(j!=i)
{
int mx=(x[i]+x[j])/2,my=(y[i]+y[j])/2;
int dx=(x[j]-x[i])/2,dy=(y[j]-y[i])/2;
vec.pb(Point(mx,my),Point(mx+dy,my-dx));
}
ans+=calc(vec,Point(x[i],y[i]));
// cerr<<ans<<endl;
}
ans/=(x2-x1);
ans/=(y2-y1);
ans/=4;
ans*=acosl(-1.0);
printf("%.15lf\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3724kb
input:
0 0 2 2 2 3 1 1 3
output:
8.377580409572783
result:
ok found '8.3775804', expected '8.3775804', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
0 0 2 2 2 5 1 1 3
output:
37.699111843077517
result:
ok found '37.6991118', expected '37.6991118', error '0.0000000'
Test #3:
score: -100
Time Limit Exceeded
input:
-2911 2151 336 5941 2000 -83 79 -94 47 48 -29 -47 64 84 75 -44 -86 -58 -11 -31 58 20 53 80 -19 -82 74 -60 -26 8 -68 -42 -61 -14 12 -58 -18 92 10 35 -26 71 64 76 89 -80 6 70 4 -96 -99 95 -80 -3 -22 71 -89 -75 17 -35 -82 -59 95 60 48 -74 50 -82 90 -26 5 -75 -31 -45 85 85 14 -70 -57 59 46 55 13 -23 60 ...