QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#53543#2309. 保镖not_so_organic100 ✓2273ms10520kbC++113.8kb2022-10-05 13:18:282022-10-05 13:18:32

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-05 13:18:32]
  • 评测
  • 测评结果:100
  • 用时:2273ms
  • 内存:10520kb
  • [2022-10-05 13:18:28]
  • 提交

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