QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#762499#9704. Polycutucup-team1004AC ✓18ms15520kbC++174.2kb2024-11-19 15:15:102024-11-19 15:15:18

Judging History

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

  • [2024-11-19 15:15:18]
  • 评测
  • 测评结果:AC
  • 用时:18ms
  • 内存:15520kb
  • [2024-11-19 15:15:10]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include"debug.h"
#else
#define debug(...) void()
#endif
#define all(x) (x).begin(),(x).end()
template<class T>
auto ary(T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
using ll=long long;
using ull=unsigned long long;
using ld=long double;
const int N=1e5+10;
const ld eps=1e-9;
int n,m,k;
struct vec{
	ld x,y,z;
	vec()=default;
	vec(ld a,ld b,ld c):x(a),y(b),z(c){}
}a[N];
#ifdef DEBUG
ostream& operator << (ostream &out,vec a){
	return out<<'('<<a.x<<','<<a.y<<','<<a.z<<')';
}
#endif
int sign(ld x){
	return x>eps?1:(x<-eps?-1:0);
}
vec operator + (const vec &a,const vec &b){
	return vec(a.x+b.x,a.y+b.y,a.z+b.z);
}
vec operator - (const vec &a,const vec &b){
	return vec(a.x-b.x,a.y-b.y,a.z-b.z);
}
vec operator * (const vec &a,const ld &k){
	return vec(a.x*k,a.y*k,a.z*k);
}
vec cross(const vec &a,const vec &b){
	return vec(
		a.y*b.z-a.z*b.y,
		a.z*b.x-a.x*b.z,
		a.x*b.y-a.y*b.x
	);
}
ld dot(const vec &a,const vec &b){
	return a.x*b.x+a.y*b.y+a.z*b.z;
}
ld normal(const vec &a){
	return sqrt(dot(a,a));
}
struct plane{
	int a,b,c,d;
	vec arg()const{
		return vec(a,b,c);
	}
}b[4];
ld where(plane a,vec b){
	return a.a*b.x+a.b*b.y+a.c*b.z-a.d;
}
vec calc(plane a,vec b,vec c){
	ld x=where(a,b),y=-where(a,c);
	return b*(y/(x+y))+c*(x/(x+y));
}
vector<pair<vec,int>>to[N];
vector<ld>ans;
ld volumn(int x,int y,int z,int w){
	return dot(cross(a[y]-a[x],a[z]-a[x]),a[w]-a[x])/(ld)6;
}
void solve(vector<int>V,vector<pair<int,int>>E,int k){
	if(!k){
		vector<vec>cur;
		for(int x:V)cur.push_back(a[x]);
		int m=E.size();
		vector<int>nex(m*2,-1),vis(m*2,0);
		for(int i=0;i<m;i++){
			auto [u,v]=E[i];
			to[u].push_back({a[v]-a[u],i*2});
			to[v].push_back({a[u]-a[v],i*2+1});
		}
		auto start=[&](int i){
			if(i&1)return E[i/2].second;
			else return E[i/2].first;
		};
		for(int u:V)if(!to[u].empty()){
			vec z(0,0,0);
			for(auto [p,id]:to[u]){
				p=p*((ld)1/normal(p));
				z=z+p;
			}
			z=z*((ld)1/to[u].size());
			for(auto &[p,id]:to[u]){
				p=p-z*(dot(p,z)/normal(z));
			}
			vec x=to[u][0].first;
			vec y=cross(z,x);
			auto find=[&](vec p){
				int op=sign(dot(p,y));
				if(op)return op>0?1:3;
				return sign(dot(p,x))>0?0:2;
			};
			sort(to[u].begin()+1,to[u].end(),[&](pair<vec,int>a,pair<vec,int>b){
				int p=find(a.first),q=find(b.first);
				if(p!=q)return p<q;
				return sign(dot(cross(a.first,b.first),z))>0;
			});
			for(int i=0;i<to[u].size();i++){
				int j=(i+1)%to[u].size();
				nex[to[u][j].second^1]=to[u][i].second;
			}
		}
		ld res=0;
		for(int i=0;i<m*2;i++)if(!vis[i]){
			vis[i]=1;
			for(int j=nex[i];;j=nex[j]){
				vis[j]=1;
				if(vis[nex[j]])break;
				res+=abs(volumn(V[0],start(i),start(j),start(nex[j])));
			}
		}
		ans.push_back(res);
		for(int u:V)to[u].clear();
		return;
	}
	vector<int>Vl,Vr;
	vector<pair<int,int>>El,Er;
	vector<int>Vt;
	for(int x:V){
		int op=sign(where(b[k],a[x]));
		if(op==0)Vt.push_back(x);
		if(op>=0)Vl.push_back(x);
		if(op<=0)Vr.push_back(x);
	}
	for(auto [u,v]:E){
		if(sign(where(b[k],a[u]))<0)swap(u,v);
		if(sign(where(b[k],a[u]))*sign(where(b[k],a[v]))<0){
			a[++n]=calc(b[k],a[u],a[v]);
			Vt.push_back(n),Vl.push_back(n),Vr.push_back(n);
			El.push_back({n,u}),Er.push_back({n,v});
		}else if(sign(where(b[k],a[u]))>=0){
			El.push_back({u,v});
		}else Er.push_back({u,v});
	}
	if(Vt.size()>2){
		sort(Vt.begin()+1,Vt.end(),[&](int x,int y){
			return sign(dot(cross(a[x]-a[Vt[0]],a[y]-a[Vt[0]]),b[k].arg()))>0;
		});
		for(int i=0;i<Vt.size();i++){
			int j=(i+1)%Vt.size();
			El.push_back({Vt[i],Vt[j]});
			Er.push_back({Vt[i],Vt[j]});
		}
	}
	solve(Vl,El,k-1);
	solve(Vr,Er,k-1);
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1,x,y,z;i<=n;i++){
		scanf("%d%d%d",&x,&y,&z);
		a[i]=vec(x,y,z);
	}
	vector<pair<int,int>>E(m);
	for(auto &[u,v]:E){
		scanf("%d%d",&u,&v);
		u++,v++;
	}
	for(int i=1;i<=k;i++){
		scanf("%d%d%d%d",&b[i].a,&b[i].b,&b[i].c,&b[i].d);
	}
	vector<int>V(n);
	iota(all(V),1);
	solve(V,E,k);
	sort(all(ans));
	for(auto x:ans)printf("%.15Lf\n",x);
	return 0;
}
#ifdef DEBUG
#include"debug.hpp"
#endif

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 6940kb

input:

8 12 1
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
0 1
1 3
3 2
2 0
4 5
5 7
7 6
6 4
0 4
1 5
2 6
3 7
3 0 0 1

output:

0.333333333333333
0.666666666666667

result:

ok 2 numbers

Test #2:

score: 0
Accepted
time: 1ms
memory: 6656kb

input:

4 6 1
0 0 0
0 0 3
0 2 0
1 0 0
0 1
0 2
0 3
1 2
1 3
2 3
1 1 1 0

output:

0.000000000000000
1.000000000000000

result:

ok 2 numbers

Test #3:

score: 0
Accepted
time: 4ms
memory: 8776kb

input:

1549 3983 3
32 38 -38
-9 -29 -47
6 36 -51
0 37 -49
-31 26 -29
-29 -35 -23
24 -21 -54
-27 -18 55
31 -18 32
10 -3 54
-23 -33 50
-4 14 58
24 19 39
-15 57 22
46 12 -1
15 -24 -55
-42 15 -12
-36 15 -25
-40 -32 0
10 -37 -48
-34 -22 48
30 32 -46
12 -55 -28
-13 -49 -28
23 56 -6
31 7 -55
-7 -59 -16
17 -60 -2
...

output:

0.000000000000000
731.251644135940632
14338.233675781045976
71702.192621034646557
75029.313549385372134
178008.756759801886858
202716.114964342688864
209056.470118851752247

result:

ok 8 numbers

Test #4:

score: 0
Accepted
time: 2ms
memory: 8688kb

input:

870 2162 3
-6 -15 33
19 25 12
-28 -6 -21
17 27 -16
0 10 33
-30 -19 -1
18 10 28
-28 20 -10
-8 -29 -13
-3 -30 19
-12 -30 14
6 -28 22
-19 25 11
6 33 1
9 -27 22
-3 31 10
-18 -24 20
-4 26 -25
17 30 -3
-17 -27 -10
-17 -27 16
12 -2 34
-19 -25 -12
13 26 16
25 17 17
-25 17 -20
11 7 -34
-4 -3 -35
-17 -30 3
-2...

output:

4717.213682575672347
10575.665207554135972
11042.404729981179599
13892.444609451443040
15124.558174544206762
20567.050109275134567
29727.361032744975997
74646.802453873251771

result:

ok 8 numbers

Test #5:

score: 0
Accepted
time: 0ms
memory: 8360kb

input:

100 289 3
-20 26 5
17 14 -1
8 -28 5
0 -29 -13
5 -8 29
20 14 12
25 -10 -7
16 6 32
-20 -4 -28
12 21 19
1 26 23
26 0 14
6 12 -19
9 -15 -27
3 -20 17
7 26 12
20 -26 -3
-9 30 2
-12 -17 4
-23 3 -25
18 14 21
-24 19 -10
-2 14 -23
-12 11 26
-10 -24 -8
4 26 18
-14 -20 -21
20 12 3
-15 14 22
-14 29 8
-21 3 -27
2...

output:

161.893709297982977
573.399185021190621
3693.839524653142350
7833.515926634312736
9917.759185694609075
16560.525704370520925
21053.591667741407052
33248.641763253500933

result:

ok 8 numbers

Test #6:

score: 0
Accepted
time: 18ms
memory: 13780kb

input:

10000 29993 2
-820 6143 -2468
-5339 2920 -1416
810 6736 377
-4708 3289 -2210
-5728 1772 3918
-484 4561 4607
5298 -554 -5072
5509 -2244 -3857
-2890 -2069 6289
682 -6162 -2305
-1054 -4282 5361
3379 3361 -5667
290 3972 -5456
5213 4454 668
6579 -1310 -857
-611 -237 6556
4812 4673 1123
-1066 -2288 6335
1...

output:

111020528752.921601280570030
202570778719.334404140710831
408682698803.956904381513596
535041892732.620423942804337

result:

ok 4 numbers

Test #7:

score: 0
Accepted
time: 11ms
memory: 13656kb

input:

8463 25211 3
627 -330 -215
460 -69 -387
406 380 -233
-254 651 391
196 742 295
-257 85 -523
289 -128 -491
-267 658 -167
612 108 -192
550 212 430
375 -636 -320
34 51 -530
-526 608 100
26 -408 -554
424 -656 68
-655 316 170
733 -154 85
-457 647 -37
453 -282 394
-38 375 558
-703 256 -135
-363 -359 -514
-...

output:

61629794.847391681185400
78102721.722661017949576
89032895.546470520945149
168429903.230674581092899
179587902.099633122488740
186794039.343644854830927
236926846.657173648156459
363532060.052350573154399

result:

ok 8 numbers

Test #8:

score: 0
Accepted
time: 0ms
memory: 8432kb

input:

50 144 1
-33 -10 -11
25 23 0
-31 15 -21
6 -27 26
-16 -24 22
7 20 -31
4 9 -36
-36 30 6
20 27 -9
17 29 1
11 -39 6
-23 -24 -7
-14 -11 34
39 1 -16
-23 -22 -11
33 11 -15
24 6 -31
-40 22 -4
39 5 -8
-39 4 19
22 -25 23
35 10 -11
-3 16 35
5 29 -22
-36 31 0
35 -28 7
-38 23 -8
-19 23 31
-33 25 -14
0 -9 -37
42 ...

output:

73689.287075817618970
129946.212924182381037

result:

ok 2 numbers

Test #9:

score: 0
Accepted
time: 18ms
memory: 15520kb

input:

10000 29987 3
1363 -471 2354
2882 -1315 1369
-3050 1267 909
3290 -1224 447
-3295 2331 26
1049 -4163 -438
-2217 -1486 567
2326 951 -959
-1414 446 -2338
790 -4044 399
-100 -3012 1367
2781 -2417 1278
2260 -3857 512
-2243 2993 -1410
3253 -2522 243
-1216 3830 1174
-632 1092 -2409
-3002 -20 246
38 -3027 1...

output:

62773682.995097639763117
359318605.416114033345366
2137476475.711665866896510
3366529531.787400148110464
6779053596.526363016571850
25055646791.036852203309536
39297899211.222171138972044
58744696032.637669272720814

result:

ok 8 numbers

Test #10:

score: 0
Accepted
time: 3ms
memory: 9016kb

input:

1000 2994 3
-667 257 -318
218 -487 475
388 -779 -167
-309 306 710
-94 604 650
112 -297 621
463 635 -261
581 -576 78
789 128 276
-778 -329 -225
-404 -172 -647
144 -138 -745
426 -524 326
642 463 -292
521 656 -181
-725 142 445
-118 -572 -661
-480 -733 56
-767 -358 198
516 230 -548
-160 847 0
513 595 44...

output:

16936325.374090761659318
27603547.359886159265443
30215233.314450199264684
91603154.568647180240077
124869680.079084019402217
319262690.492523610271746
566969902.953765635960735
1175795624.857552434084937

result:

ok 8 numbers

Test #11:

score: 0
Accepted
time: 15ms
memory: 15304kb

input:

10000 29994 3
2828 -2410 5063
4981 -450 -4482
-4800 1373 -5219
-1666 -201 -5824
-892 4306 -1810
-3056 3071 3058
-1462 2142 -5389
-3061 1120 -5679
-8096 2118 222
3301 4147 -1305
-4571 3650 -2376
1381 -106 5872
-2168 429 -5853
9488 -606 595
2959 4234 339
-6848 2888 210
-1075 2342 -5270
-6211 417 3851
...

output:

3175212044.211785970488563
7791559044.323700250126421
9680741614.756551797501743
18789610196.058420313522220
43006765099.738518614321947
47218239518.265608195215464
397827021304.767590433359146
511630931488.711157977581024

result:

ok 8 numbers