QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#762499 | #9704. Polycut | ucup-team1004 | AC ✓ | 18ms | 15520kb | C++17 | 4.2kb | 2024-11-19 15:15:10 | 2024-11-19 15:15:18 |
Judging History
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
詳細信息
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