QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#34426 | #876. Big Brother | Froggygua | WA | 234ms | 58928kb | C++17 | 5.6kb | 2022-06-08 22:16:24 | 2022-06-08 22:16:25 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const double eps=1e-10;
const double PI=acos(-1.0);
//Vector可以用Point来表示
struct Point{
double x,y;
Point(double _x=0,double _y=0):x(_x),y(_y){}
//相等
friend bool operator ==(const Point &a,const Point &b){
return fabs(a.x-b.x)<eps&&fabs(a.y-b.y)<eps;
}
//不相等
friend bool operator !=(const Point &a,const Point &b){
return !(a==b);
}
//相加
friend Point operator + (const Point &a,const Point &b){
return Point(a.x+b.x,a.y+b.y);
}
//相减
friend Point operator - (const Point &a,const Point &b){
return Point(a.x-b.x,a.y-b.y);
}
//点积
friend double operator * (const Point &a,const Point &b){
return a.x*b.x+a.y*b.y;
}
//叉积
friend double operator % (const Point &a,const Point &b){
return a.x*b.y-a.y*b.x;
}
//长度
inline double len(){
return sqrt(x*x+y*y);
}
//单位向量
Point unit(){
double l=len();
return Point(x/l,y/l);
}
//求单位法向量
inline Point normal(){
double l=len();
return Point(-y/l,x/l);
}
//点从下往上排序
inline bool operator < (Point b){
return fabs(y-b.y)<eps?x<b.x:y<b.y;
}
//平面直角坐标系上半部分优先
inline bool Quad(){
return y>eps||(fabs(y)<=eps&&x>=-eps);
}
};
inline Point operator * (double k,Point a){
return Point(a.x*k,a.y*k);
}
//两个向量的夹角
inline double Angle(Point a,Point b){
//return acos(a*b/a.len()/b.len());
double tmp=atan2(b.y,b.x)-atan2(a.y,a.x);
while(tmp>=PI+eps)tmp-=2*PI;
while(tmp<=-PI-eps)tmp+=2*PI;
return tmp;
}
//判断两个向量是否平行
inline bool Para(Point a,Point b){
return fabs(a%b)<=eps;
}
//判断向量a是否在向量b的左侧
inline bool Left(Point a,Point b){
return b%a>eps;
}
//逆时针旋转p后的向量
inline Point Rotate(Point a,double p){
return Point(a.x*cos(p)-a.y*sin(p),a.x*sin(p)+a.y*cos(p));
}
//绕LTL逆时针排序
//直线
struct Line{
Point p[2];
Line(Point a=Point(0,0),Point b=Point(0,0)){p[0]=a,p[1]=b;}
inline Point& operator [] (int i){
return p[i];
}
inline Point v(){
return p[1]-p[0];
}
};
//直线交点
inline Point Cross(Line a,Line b){
return a[0]+((b[0]-a[0])%(b[1]-a[0]))/((a[1]-a[0])%(b[1]-b[0]))*(a[1]-a[0]);
}
//多边形
typedef vector<Point> Poly;
//面积
double Area(Poly A){
double tot=0;
for(int i=0;i<(int)A.size()-1;++i){
tot+=A[i]%A[i+1];
}
tot+=A[(int)A.size()-1]%A[0];
return fabs(tot)/2.0;
}
//周长
double C(Poly A){
double tot=0;
for(int i=0;i<(int)A.size()-1;++i){
tot+=(A[i+1]-A[i]).len();
}
tot+=(A[A.size()-1]-A[0]).len();
return tot;
}
//重心
Point Cent(Poly A){
double x=0,y=0,m=0;
for(int i=1;i<(int)A.size()-1;++i){
double tmp=(A[i]-A[0])%(A[i+1]-A[0]);
x+=tmp*(A[0].x+A[i].x+A[i+1].x)/3.0;
y+=tmp*(A[0].y+A[i].y+A[i+1].y)/3.0;
m+=tmp;
}
return Point(x/m,y/m);
}
//求凸包
Poly Convex(Poly A){
Point LTL=(*min_element(A.begin(),A.end())); //Lower Then Left
sort(A.begin(),A.end(),[&](Point a,Point b){
a=a-LTL,b=b-LTL;
return Para(a,b)?a.len()<b.len():Left(b,a);
});
Poly st;
for(auto p:A){
while(st.size()>1&&!Left(p-st[(int)st.size()-2],st.back()-st[(int)st.size()-2]))st.pop_back();
st.push_back(p);
}
return st;
}
// 求点是否在多边形内(单次询问,可以是凹多边形)
inline bool Inside_1(Poly A,Point p){
double tot=0;
for(int i=0;i<(int)A.size();++i)tot+=Angle(A[i]-p,A[(i+1)%A.size()]-p);
return fabs(tot)>=eps;
}
//多组询问
inline bool Inside_2(Poly &A,Point p){
if(p==A[0])return true;
if(Left(p-A[0],A[A.size()-1]-A[0])||Left(A[1]-A[0],p-A[0]))return false;
int pos=lower_bound(A.begin(),A.end()-1,p,[&](Point a,Point b){
a=a-A[0],b=b-A[0];
return Para(a,b)?a.len()<b.len():Left(b,a);
})-A.begin();
return !Left(A[pos]-A[pos-1],p-A[pos-1])&&A[0]<p;
}
//半平面交(HalfPlaneIntersection) <向量左侧>
inline bool cmpang(Point a,Point b){
return a.Quad()^b.Quad()?a.Quad()<b.Quad():Left(b,a);
}
inline bool operator <(Line a,Line b){
return Para(a.v(),b.v())&&(a.v()*b.v()>eps)?Left(a[0]-b[0],b.v()):cmpang(a.v(),b.v());
}
Poly HPI(vector<Line> L){
vector<Line> q(L.size()+10);
static int l,r;
sort(L.begin(),L.end());
Poly R;
r=1,q[l=1]=L[0];
for(int i=1;i<(int)L.size();++i){
if(!cmpang(q[r].v(),L[i].v()))continue;
while(l<r&&Left(L[i].v(),Cross(q[r],q[r-1])-L[i][0]))--r;
while(l<r&&Left(L[i].v(),Cross(q[l],q[l+1])-L[i][0]))++l;
q[++r]=L[i];
}
while(l<r&&Left(q[l].v(),Cross(q[r],q[r-1])-q[l][0]))--r;
while(l<r&&Left(q[r].v(),Cross(q[l],q[l+1])-q[r][0]))++l;
q[r+1]=q[l];
for(int i=l;i<=r;++i){
R.push_back(Cross(q[i],q[i+1]));
}
return R;
}
//Minkowski
inline Poly operator + (const Poly &A,const Point &p){
Poly C=A;
for(auto &t:C)t=t+p;
return C;
}
inline Poly operator + (const Poly &A,const Poly &B){
if(A.empty())return B;
if(B.empty())return A;
if(A.size()==1)return B+A[0];
if(B.size()==1)return A+B[0];
Poly R;
int i=0,j=0;
R.push_back(A[0]+B[0]);
while(true){
Point vA=A[(i+1)%A.size()]-A[i],vB=B[(j+1)%B.size()]-B[j];
if(Para(vA,vB)?vA.Quad()==vB.Quad():Left(vA,vB)){
i=(i+1)%A.size();
}
else{
j=(j+1)%B.size();
}
R.push_back(A[i]+B[j]);
if(!i&&!j)break;
}
R.pop_back();
return R;
}
int n;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.setf(ios::fixed);
cout.precision(10);
vector<Line> L;
cin>>n;
Poly A(n);
for(int i=0;i<n;++i){
cin>>A[i].x>>A[i].y;
}
for(int i=0;i<n;++i){
L.emplace_back(A[(i+1)%n],A[i]);
}
cout<<Area(HPI(L))<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3804kb
input:
8 0 0 0 1 1 1 1 2 2 2 2 1 3 1 3 0
output:
1.0000000000
result:
ok "1.000000000"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
8 0 0 0 2 1 2 1 1 2 1 2 2 3 2 3 0
output:
0.0000000000
result:
ok "0.000000000"
Test #3:
score: 0
Accepted
time: 2ms
memory: 3880kb
input:
6 140 62 97 141 68 156 129 145 153 176 130 109
output:
48.8034950021
result:
ok "48.803495002"
Test #4:
score: 0
Accepted
time: 2ms
memory: 3828kb
input:
3 198 165 322 122 242 84
output:
4076.0000000000
result:
ok "4076.000000000"
Test #5:
score: 0
Accepted
time: 2ms
memory: 3800kb
input:
15 0 250 30 250 125 250 180 250 250 250 250 100 250 80 250 0 140 0 100 0 73 0 0 0 0 2 0 30 0 90
output:
62500.0000000000
result:
ok "62500.000000000"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3752kb
input:
16 146 145 109 229 139 301 164 385 221 433 309 419 405 420 447 369 501 308 498 229 471 150 456 75 391 39 308 47 227 39 166 73
output:
114711.3646559959
result:
ok "114711.364655996"
Test #7:
score: 0
Accepted
time: 2ms
memory: 3736kb
input:
6 160 210 200 210 200 300 280 300 200 170 200 80
output:
0.0000000000
result:
ok "0.000000000"
Test #8:
score: 0
Accepted
time: 2ms
memory: 3788kb
input:
8 198 165 230 113 246 117 281 161 266 36 247 68 228 79 200 30
output:
63.7023612504
result:
ok "63.702361250"
Test #9:
score: 0
Accepted
time: 2ms
memory: 3792kb
input:
14 198 165 274 226 258 318 297 348 339 309 372 360 336 265 347 203 388 161 346 123 306 155 293 87 261 112 242 84
output:
2189.0016479133
result:
ok "2189.001647913"
Test #10:
score: 0
Accepted
time: 2ms
memory: 3836kb
input:
150 9956003 4338159 9912302 4099714 9868603 3861269 9803272 3631902 9737943 3402535 9725452 3366405 9712963 3330276 9696862 3286153 9680763 3242031 9604920 3061837 9529080 2881643 9480997 2784399 9432916 2687155 9193856 2313907 8954799 1940659 8617533 1583544 8280269 1226429 8207226 1165339 8134185 ...
output:
77922149990018.1250000000
result:
ok "77922149990018.218750000"
Test #11:
score: 0
Accepted
time: 3ms
memory: 3948kb
input:
1000 9999605 4937170 9999012 4905760 9998421 4874350 9997433 4842949 9996447 4811549 9995065 4780163 9993685 4748778 9991908 4717412 9990134 4686047 9987963 4654706 9985795 4623366 9983230 4592055 9980668 4560744 9977710 4529467 9974755 4498191 9971405 4466954 9968057 4435718 9964314 4404526 9960574...
output:
78537708558542.0781250000
result:
ok "78537708558542.031250000"
Test #12:
score: 0
Accepted
time: 25ms
memory: 9032kb
input:
50000 10000000 4998743 9999998 4998115 9999999 4997487 9999998 4996858 9999999 4996230 9999997 4995601 9999997 4994973 9999995 4994345 9999996 4993717 9999994 4993088 9999994 4992460 9999992 4991832 9999992 4991204 9999990 4990575 9999990 4989947 9999987 4989318 9999987 4988690 9999984 4988062 99999...
output:
78539327974559.6093750000
result:
ok "78539327974559.937500000"
Test #13:
score: 0
Accepted
time: 114ms
memory: 30916kb
input:
250000 10000000 4999749 9999999 4999623 10000000 4999497 9999999 4999371 10000000 4999246 9999999 4999120 10000000 4998995 9999999 4998869 10000000 4998743 9999999 4998617 10000000 4998492 9999999 4998366 10000000 4998241 9999999 4998115 10000000 4997989 9999998 4997863 9999999 4997738 9999998 49976...
output:
78525334096415.2343750000
result:
ok "78525334096415.250000000"
Test #14:
score: 0
Accepted
time: 234ms
memory: 58212kb
input:
500000 10000000 4999874 9999999 4999811 10000000 4999749 9999999 4999686 10000000 4999623 9999999 4999560 10000000 4999497 9999999 4999434 10000000 4999372 9999999 4999309 10000000 4999246 9999999 4999183 10000000 4999120 9999999 4999057 10000000 4998995 9999999 4998932 10000000 4998869 9999999 4998...
output:
78479009888752.8593750000
result:
ok "78479009888752.796875000"
Test #15:
score: 0
Accepted
time: 1ms
memory: 3728kb
input:
150 9725000 5000000 9496052 4811560 9932639 4585795 9464516 4436001 9658831 4212018 9401664 4064398 9794486 3768986 9307937 3699357 9462178 3446106 9183994 3343440 9522050 2986654 9030702 2999142 9140549 2723714 8849139 2668879 9122960 2260712 8640576 2354967 8702951 2065077 8406477 2059608 8608394 ...
output:
11331974361764.5527343750
result:
ok "11331974361764.560546875"
Test #16:
score: 0
Accepted
time: 3ms
memory: 3888kb
input:
1000 9725000 5000000 9499911 4971726 9949609 4937799 9499200 4915183 9723507 4881261 9497779 4858652 9946482 4813434 9495648 4802144 9719032 4762596 9492806 4745667 9940232 4689187 9489256 4689230 9711575 4644081 9484996 4632843 9930861 4565137 9480028 4576513 9701143 4525791 9474353 4520250 9918375...
output:
302585512646.1289062500
result:
ok "302585512646.140625000"
Test #17:
score: 0
Accepted
time: 22ms
memory: 8796kb
input:
50000 9725000 5000000 9499999 4999435 9949999 4998756 9499999 4998304 9724999 4997625 9499999 4997173 9949998 4996268 9499998 4996042 9724997 4995250 9499997 4994911 9949996 4993780 9499995 4993780 9724994 4992875 9499993 4992649 9949992 4991292 9499992 4991518 9724990 4990500 9499989 4990387 994998...
output:
121175133.1425781250
result:
ok "121175133.132812500"
Test #18:
score: 0
Accepted
time: 104ms
memory: 30856kb
input:
250000 9725000 5000000 9499999 4999887 9949999 4999752 9499999 4999661 9724999 4999525 9499999 4999435 9949999 4999254 9499999 4999209 9724999 4999050 9499999 4998983 9949999 4998756 9499999 4998756 9724999 4998575 9499999 4998530 9949999 4998259 9499999 4998304 9724999 4998100 9499999 4998078 99499...
output:
4772368.0546875000
result:
ok "4772368.076171875"
Test #19:
score: 0
Accepted
time: 222ms
memory: 58928kb
input:
500000 9725000 5000000 9499999 4999944 9949999 4999876 9499999 4999831 9724999 4999763 9499999 4999718 9949999 4999627 9499999 4999605 9724999 4999525 9499999 4999492 9949999 4999378 9499999 4999378 9724999 4999288 9499999 4999265 9949999 4999130 9499999 4999152 9724999 4999050 9499999 4999039 99499...
output:
1169025.6074218750
result:
ok "1169025.593750000"
Test #20:
score: 0
Accepted
time: 2ms
memory: 3864kb
input:
72 4 50 4 51 5 56 6 60 7 63 9 68 10 70 13 75 15 78 18 82 19 83 23 86 26 88 31 91 33 92 38 94 41 95 45 96 50 97 51 97 56 96 60 95 63 94 68 92 70 91 75 88 78 86 82 83 83 82 86 78 88 75 91 70 92 68 94 63 95 60 96 56 97 51 97 50 96 45 95 41 94 38 92 33 91 31 88 26 86 23 83 19 82 18 78 15 75 13 70 10 68 ...
output:
6435.0000000000
result:
ok "6435.000000000"
Test #21:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
72 4 50 4 51 5 56 6 60 7 63 9 68 10 70 13 75 15 78 18 82 20 82 23 86 26 88 31 91 33 92 38 94 41 95 45 96 50 97 51 97 56 96 60 95 63 94 68 92 70 91 75 88 78 86 82 83 83 82 86 78 88 75 91 70 91 68 94 63 95 60 96 56 97 51 97 50 96 45 95 41 94 38 92 33 91 31 88 26 86 23 83 19 82 18 78 15 75 13 70 10 68 ...
output:
4180.1000000000
result:
ok "4180.100000000"
Test #22:
score: 0
Accepted
time: 1ms
memory: 3804kb
input:
336 10 500 10 501 11 512 12 522 13 531 14 539 15 546 16 552 18 563 19 568 21 577 22 581 25 592 27 599 30 609 31 612 35 623 38 631 40 636 43 643 47 652 52 663 53 665 59 676 64 685 68 692 71 697 76 705 83 716 85 719 92 729 97 736 105 747 108 751 115 760 119 765 128 776 133 782 139 789 146 797 154 806 ...
output:
708179.0000000000
result:
ok "708179.000000000"
Test #23:
score: 0
Accepted
time: 3ms
memory: 3832kb
input:
336 10 500 10 501 11 512 12 522 13 531 14 539 15 546 16 552 18 563 19 568 21 577 22 581 25 592 27 599 30 609 31 612 35 623 38 631 40 636 43 643 47 652 52 663 53 665 59 676 64 685 68 692 71 697 76 705 83 716 85 719 92 729 97 736 105 747 109 750 115 760 119 765 128 776 133 782 139 789 146 797 154 806 ...
output:
696280.0758658010
result:
ok "696280.075865801"
Test #24:
score: 0
Accepted
time: 3ms
memory: 4020kb
input:
1576 22 5000 22 5001 23 5026 24 5050 25 5073 26 5095 27 5116 28 5136 29 5155 30 5173 31 5190 32 5206 33 5221 34 5235 35 5248 37 5273 38 5285 40 5308 41 5319 43 5340 44 5350 46 5369 47 5378 49 5395 52 5420 53 5428 56 5451 58 5466 61 5488 62 5495 65 5515 67 5528 70 5547 74 5572 75 5578 79 5601 82 5618...
output:
73741747.0000000000
result:
ok "73741747.000000000"
Test #25:
score: 0
Accepted
time: 3ms
memory: 3940kb
input:
1576 22 5000 22 5001 23 5026 24 5050 25 5073 26 5095 27 5116 28 5136 29 5155 30 5173 31 5190 32 5206 33 5221 34 5235 35 5248 37 5273 38 5285 40 5308 41 5319 43 5340 44 5350 46 5369 47 5378 49 5395 52 5420 53 5428 56 5451 58 5466 61 5488 62 5495 65 5515 67 5528 70 5547 74 5572 75 5578 79 5601 82 5618...
output:
73705049.0762995631
result:
ok "73705049.076299563"
Test #26:
score: 0
Accepted
time: 7ms
memory: 4308kb
input:
7328 7 50000 7 50001 8 50056 9 50110 10 50163 11 50215 12 50266 13 50316 14 50365 15 50413 16 50460 17 50506 18 50551 19 50595 20 50638 21 50680 22 50721 23 50761 24 50800 25 50838 26 50875 27 50911 28 50946 29 50980 30 51013 31 51045 32 51076 33 51106 34 51135 35 51163 37 51218 38 51245 40 51298 41...
output:
7448951491.0000000000
result:
ok "7448951491.000000000"
Test #27:
score: 0
Accepted
time: 7ms
memory: 4332kb
input:
7328 7 50000 7 50001 8 50056 9 50110 10 50163 11 50215 12 50266 13 50316 14 50365 15 50413 16 50460 17 50506 18 50551 19 50595 20 50638 21 50680 22 50721 23 50761 24 50800 25 50838 26 50875 27 50911 28 50946 29 50980 30 51013 31 51045 32 51076 33 51106 34 51135 35 51163 37 51218 38 51245 40 51298 41...
output:
7448332528.5340909958
result:
ok "7448332528.534090042"
Test #28:
score: 0
Accepted
time: 25ms
memory: 8540kb
input:
33920 55 500000 55 500001 56 500119 57 500236 58 500352 59 500467 60 500581 61 500694 62 500806 63 500917 64 501027 65 501136 66 501244 67 501351 68 501457 69 501562 70 501666 71 501769 72 501871 73 501972 74 502072 75 502171 76 502269 77 502366 78 502462 79 502557 80 502651 81 502744 82 502836 83 5...
output:
741575176515.0000000000
result:
ok "741575176515.000000000"
Test #29:
score: 0
Accepted
time: 26ms
memory: 8560kb
input:
33920 55 500000 55 500001 56 500119 57 500236 58 500352 59 500467 60 500581 61 500694 62 500806 63 500917 64 501027 65 501136 66 501244 67 501351 68 501457 69 501562 70 501666 71 501769 72 501871 73 501972 74 502072 75 502171 76 502269 77 502366 78 502462 79 502557 80 502651 81 502744 82 502836 83 5...
output:
741573412548.7573242188
result:
ok "741573412548.757324219"
Test #30:
score: 0
Accepted
time: 94ms
memory: 29828kb
input:
157336 187 5000000 187 5000001 188 5000256 189 5000510 190 5000763 191 5001015 192 5001266 193 5001516 194 5001765 195 5002013 196 5002260 197 5002506 198 5002751 199 5002995 200 5003238 201 5003480 202 5003721 203 5003961 204 5004200 205 5004438 206 5004675 207 5004911 208 5005146 209 5005380 210 5...
output:
74106620545235.0000000000
result:
ok "74106620545235.000000000"
Test #31:
score: 0
Accepted
time: 103ms
memory: 29172kb
input:
157336 187 5000000 187 5000001 188 5000256 189 5000510 190 5000763 191 5001015 192 5001266 193 5001516 194 5001765 195 5002013 196 5002260 197 5002506 198 5002751 199 5002995 200 5003238 201 5003480 202 5003721 203 5003961 204 5004200 205 5004438 206 5004675 207 5004911 208 5005146 209 5005380 210 5...
output:
74103087971323.8750000000
result:
ok "74103087971323.890625000"
Test #32:
score: -100
Wrong Answer
time: 3ms
memory: 3944kb
input:
1000 2600927 1831555 2984114 2324333 2787576 1961497 2689538 1755826 3028761 2094323 3008306 1946570 2887360 1607548 2631170 1248827 2470347 1030200 2599775 976740 2355502 478504 3115957 1757729 3013991 1652055 3820728 3275946 3463130 2975465 2475784 1734142 1806440 809618 1228787 158466 889070 1047...
output:
nan
result:
wrong output format Expected double, but "nan" found