QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#454049 | #876. Big Brother | grass8cow# | RE | 1ms | 4400kb | C++17 | 2.3kb | 2024-06-24 16:08:42 | 2024-06-24 16:08:44 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const double eps=1e-10;
int n,m,sum;
struct vec
{
double x,y;
vec(double X=0,double Y=0):x(X),y(Y){}
vec operator+(const vec&a)const
{
return vec(x+a.x,y+a.y);
}
vec operator-(const vec&a)const
{
return vec(x-a.x,y-a.y);
}
void operator+=(const vec&a)
{
this->x+=a.x,this->y+=a.y;
}
void operator-=(const vec&a)
{
this->x-=a.x,this->y-=a.y;
}
vec operator*(const double&a)const
{
return vec(x*a,y*a);
}
vec operator/(const double&a)const
{
return vec(x/a,y/a);
}
void operator*=(const double&a)
{
this->x*=a,this->y*=a;
}
void operator/=(const double&a)
{
this->x/=a,this->y/=a;
}
}Q[1100],M[1100];
double cp(vec A,vec B)//叉积
{
return A.x*B.y-A.y*B.x;
}
double pp(vec A,vec B)//点积
{
return A.x*B.x+A.y*B.y;
}
struct line
{
vec A,B;
double K;
line(vec a,vec b):A(a),B(b){K=atan2(B.y,B.x);}//按极角排序
line(){}
bool operator<(const line&a)const
{
return K<a.K;
}
}P[1100],T[1100];
int st,en;
vec get(line A,line B)//求交点
{
vec C=A.A-B.A;
double t=cp(B.B,C)/cp(A.B,B.B);
return A.A+A.B*t;
}
void work()
{
st=en=1;
T[st]=P[1];
for(int i=2;i<=sum;i++)
{
while(st<en&&cp(P[i].B,M[en-1]-P[i].A)<=eps)//踢出队尾,交点在当前边右侧
{
--en;
}
while(st<en&&cp(P[i].B,M[st]-P[i].A)<=eps)//踢出队首,交点在当前边右侧
{
++st;
}
T[++en]=P[i];
if(fabs(cp(T[en].B,T[en-1].B))<=eps)//平行
{
en--;
if(cp(T[en].B,P[i].A-T[en].A)>eps)//取更左边那个
{
T[en]=P[i];
}
}
if(st<en)//有多个边在集合中,加入交点
{
M[en-1]=get(T[en-1],T[en]);
}
}
while(st<en&&cp(T[st].B,M[en-1]-T[st].A)<=eps)
{
--en;
}
if(en-st<=1)
{
return ;
}
M[en]=get(T[st],T[en]);
}
void solve()
{
double ans=0;
for(int i=st;i<=en;i++)//计算面积
{
int to=i+1;
if(i==en)
{
to=st;
}
ans+=cp(M[i],M[to]);
}
printf("%.10lf",ans/2);
}
int main()
{
int m;
cin>>m;
for(int j=1;j<=m;j++)
{
scanf("%lf%lf",&Q[j].x,&Q[j].y);
}
reverse(Q+1,Q+m+1);
for(int j=1;j<=m;j++)
{
++sum;
int to=j+1;
if(j==m)
{
to=1;
}
P[sum]=line(Q[j],Q[to]-Q[j]);
}
sort(P+1,P+sum+1);//极角排序
work();
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4240kb
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: 4224kb
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: 0ms
memory: 4376kb
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: 0ms
memory: 4400kb
input:
3 198 165 322 122 242 84
output:
4076.0000000000
result:
ok "4076.000000000"
Test #5:
score: 0
Accepted
time: 0ms
memory: 4208kb
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: 0ms
memory: 4328kb
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: 0ms
memory: 4328kb
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: 0ms
memory: 4364kb
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: 0ms
memory: 4392kb
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: 0ms
memory: 4388kb
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: 1ms
memory: 4372kb
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.0937500000
result:
ok "78537708558542.031250000"
Test #12:
score: -100
Runtime Error
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...