QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#53543 | #2309. 保镖 | not_so_organic | 100 ✓ | 2273ms | 10520kb | C++11 | 3.8kb | 2022-10-05 13:18:28 | 2022-10-05 13:18:32 |
Judging History
answer
#include<bits/stdc++.h>
#define db __float128
#define N 100005
#define rep(i,x,y) for(int i=x,i##end=y;i<=i##end;++i)
const db eps=1e-10;
inline db _reps(){return rand()/(db)RAND_MAX;}
inline db reps(){int ty=rand()&1?1:-1; return _reps()*eps*ty;}
inline int eq(const db&p){return p<-eps?-1:p>eps;}
inline int eq(const db&x,const db&y){return eq(x-y);}
struct point{
db x,y;
inline point operator+(const point&p)const{return point{x+p.x,y+p.y};}
inline point operator-(const point&p)const{return point{x-p.x,y-p.y};}
inline point operator*(const db&p)const{return point{x*p,y*p};}
inline point operator/(const db&p)const{return point{x/p,y/p};}
// multiply cross
inline db operator^(const point&p)const{return x*p.y-y*p.x;}
// point multiply
inline db operator&(const point&p)const{return x*p.x+y*p.y;}
inline db norm2(){return x*x+y*y;}
inline db norm(){return sqrt(norm2());}
inline void inv(){std::swap(x,y); x=-x;}
} rec[4];
int n,cnt;
bool vis[2005][2005];
struct vector{
db x,y,z;
inline vector operator+(const vector&p)const{return vector{x+p.x,y+p.y,z+p.z};}
inline vector operator-(const vector&p)const{return vector{x-p.x,y-p.y,z-p.z};}
inline vector operator^(const vector&p)const{return vector{y*p.z-z*p.y,z*p.x-x*p.z,x*p.y-y*p.x};}
inline db operator&(const vector&p)const{return x*p.x+y*p.y+z*p.z;}
inline void rnd(){x+=reps(),y+=reps(),z+=reps();}
} poi[N];
inline point intersection(point a1,point a2,point b1,point b2){
point a=a2-a1,b=b2-b1,c=b1-a1;
return a1+(a*((b^c)/(b^a)));
}
struct plane{
int id[3];
inline plane(int x=0,int y=0,int z=0){id[0]=x,id[1]=y,id[2]=z;}
inline vector norm(){return (poi[id[1]]-poi[id[0]])^(poi[id[2]]-poi[id[0]]);}
} f[N],cpy[N];
inline bool isplane(plane x,vector y){return ((y-poi[x.id[0]])&x.norm())>0;}
inline db angle(point x,point y){return atan2(x^y,x&y);}
inline db calc(point x,point y,db r){
point p=(x-y)/(x-y).norm();
point q=p; p.inv();
point mid=intersection(x,y,point{0,0},p);
if(mid.norm()>r) return r*r*angle(x,y)/2;
db d=sqrt(r*r-mid.norm2());
point w1=mid+(q*d),w2=mid-(q*d);
int b1=eq(x.norm2(),r*r)==1,b2=eq(y.norm2(),r*r)==1;
if(b1&&b2){
if(eq((x-w1)&(y-w1))<=0)
return r*r*(angle(x,w1)+angle(w2,y))/2+(w1^w2)/2;
return r*r*angle(x,y)/2;
}
if(b1) return (r*r*angle(x,w1)+(w1^y))/2;
if(b2) return (r*r*angle(w2,y)+(x^w2))/2;
return (x^y)/2;
}
inline db merge(point o,db r){
db ret=0;
rep(i,0,3) ret+=calc(rec[i]-o,rec[i+1&3]-o,r);
return ret;
}
void convex_hull(){
f[++cnt]=plane(1,2,3),f[++cnt]=plane(3,2,1);
rep(i,4,n){
int num=0;
rep(j,1,cnt){
int ty=isplane(f[j],poi[i]);
if(!ty) cpy[++num]=f[j];
rep(k,0,2) vis[f[j].id[k]][f[j].id[(k+1)%3]]=ty;
}
rep(j,1,cnt){
rep(k,0,2){
int x=f[j].id[k],y=f[j].id[(k+1)%3];
if(vis[x][y]&&!vis[y][x]) cpy[++num]=plane(x,y,i);
}
}
rep(j,1,num) f[j]=cpy[j]; cnt=num,num=0;
}
}
int main(){
srand(time(NULL));
std::cin>>n;
double stx,sty,edx,edy;
std::cin>>stx>>sty>>edx>>edy;
rec[0]={stx,sty},rec[1]={edx,sty},rec[2]={edx,edy},rec[3]={stx,edy};
db area=0,ret=0;
area=(edx-stx)*(edy-sty);
rep(i,1,n){
double x,y; std::cin>>x>>y;
poi[i]=vector{x,y,x*x+y*y};
poi[i].rnd();
}
convex_hull();
rep(i,1,cnt){
vector center=f[i].norm();
point from1,to1,from2,to2,st,ed,a,b;
st=point{poi[f[i].id[0]].x,poi[f[i].id[0]].y},ed=point{poi[f[i].id[1]].x,poi[f[i].id[1]].y};
a=(st+ed)/2,b=ed-st,b.inv();
from1=a,to1=b+a;
st=point{poi[f[i].id[1]].x,poi[f[i].id[1]].y},ed=point{poi[f[i].id[2]].x,poi[f[i].id[2]].y};
a=(st+ed)/2,b=ed-st,b.inv();
from2=a,to2=b+a;
point inter=intersection(from1,to1,from2,to2);
db dis=(inter-point{poi[f[i].id[0]].x,poi[f[i].id[0]].y}).norm();
if(center.z>0) ret+=area-merge(inter,dis);
else ret+=merge(inter,dis);
}
printf("%.15lf\n",(double)(ret/area)+2);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 10
Accepted
time: 2ms
memory: 6376kb
input:
3 13095 53523 21222 57565 73743 46418 57815 50807 52833 4625
output:
3.000000000000000
result:
ok found '3.0000000', expected '3.0000000', error '0.0000000'
Test #2:
score: 10
Accepted
time: 4ms
memory: 6492kb
input:
4 9484 367 97414 90085 95725 630 569 58693 60899 13600 74975 88142
output:
3.432327787997702
result:
ok found '3.4323278', expected '3.4323278', error '0.0000000'
Test #3:
score: 10
Accepted
time: 4ms
memory: 6508kb
input:
4 10790 5386 64799 84295 14723 18010 57222 41585 92403 63181 86870 55689
output:
3.682702387094535
result:
ok found '3.6827024', expected '3.6827024', error '0.0000000'
Test #4:
score: 10
Accepted
time: 6ms
memory: 6656kb
input:
50 38704 2325 60204 60034 99228 41650 89041 97768 1704 14616 41456 38609 27897 88242 80544 22804 88541 87633 94127 40272 73844 62486 59949 81235 53296 25385 71483 11106 74052 60483 20132 90382 40944 65887 83369 56292 42279 95274 27798 56239 10558 79130 78751 72910 76251 65844 22875 32087 78881 65631...
output:
5.362237696628945
result:
ok found '5.3622377', expected '5.3622377', error '0.0000000'
Test #5:
score: 10
Accepted
time: 0ms
memory: 6596kb
input:
50 28457 25816 70897 86149 75027 88511 27786 70586 47267 25256 80255 85339 28146 43535 69834 90561 72144 25199 83446 82685 86984 36151 85029 81098 58436 92029 73127 89375 66855 23644 72892 89472 32664 36037 61638 92005 87457 36769 72215 25227 46267 89306 81075 84718 85139 80980 39700 29341 70127 904...
output:
15.390218950249970
result:
ok found '15.3902190', expected '15.3902190', error '0.0000000'
Test #6:
score: 10
Accepted
time: 3ms
memory: 6540kb
input:
50 38937 5259 95811 77024 34222 69979 45952 11371 23230 36463 60105 78256 73594 14004 69113 76133 40285 13837 30082 65698 34293 70041 72190 13260 56503 9621 56083 78409 62410 10082 31910 20263 47728 77202 80650 19241 43833 75883 38099 72896 24243 55155 54193 78318 28996 64287 61046 9884 31890 67752 ...
output:
17.405046478232734
result:
ok found '17.4050465', expected '17.4050465', error '0.0000000'
Test #7:
score: 10
Accepted
time: 119ms
memory: 7212kb
input:
350 33394 13615 89905 84894 68544 78221 68546 78221 68546 78225 68544 78222 68550 78223 68544 78220 68550 78221 68549 78225 68549 78218 68542 78217 68549 78219 68547 78217 68550 78220 68545 78224 68549 78223 68546 78219 68546 78224 68543 78224 68548 78220 68550 78224 68547 78218 68544 78218 68544 78...
output:
65.163075343958582
result:
ok found '65.1630753', expected '65.1630753', error '0.0000000'
Test #8:
score: 10
Accepted
time: 68ms
memory: 7080kb
input:
350 22781 2705 66821 85705 97092 24604 97095 24599 97091 24599 97097 24603 97091 24600 97090 24600 97097 24604 97090 24599 97096 24602 97095 24604 97096 24601 97098 24600 97092 24607 97096 24604 97094 24605 97098 24605 97098 24606 97090 24607 97098 24607 97093 24607 97092 24599 97094 24599 97095 246...
output:
58.500832356259174
result:
ok found '58.5008324', expected '58.5008323', error '0.0000000'
Test #9:
score: 10
Accepted
time: 2182ms
memory: 10520kb
input:
2000 12646 35314 68963 91027 55181 69707 55187 69697 55183 69693 55183 69701 55181 69702 55180 69702 55186 69694 55188 69706 55190 69702 55179 69705 55180 69699 55193 69697 55189 69702 55182 69696 55183 69699 55194 69694 55191 69699 55192 69695 55190 69697 55186 69697 55192 69702 55181 69693 55185 6...
output:
379.371708502179160
result:
ok found '379.3717085', expected '379.3717102', error '0.0000000'
Test #10:
score: 10
Accepted
time: 2273ms
memory: 10512kb
input:
2000 5111 54101 88724 89133 83572 6885 83584 6891 83578 6885 83581 6891 83572 6895 83577 6885 83582 6884 83573 6887 83573 6896 83573 6890 83570 6895 83570 6892 83574 6896 83576 6886 83577 6892 83581 6888 83578 6889 83569 6885 83582 6899 83580 6890 83572 6889 83584 6886 83582 6890 83585 6897 83584 68...
output:
305.409029759575333
result:
ok found '305.4090298', expected '305.4090486', error '0.0000001'
Extra Test:
score: 0
Extra Test Passed