QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #592491 | #7081. Cut the Plane | Afterlife | TL | 113ms | 3856kb | C++20 | 9.2kb | 2024-09-26 22:55:36 | 2024-09-26 22:55:36 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e2+1e1+7,L=12;
struct P{
int x,y;
P(int _x=0,int _y=0){x=_x,y=_y;}
};
P operator *(const P &a,const int &b)
{
return {a.x*b,a.y*b};
}
P operator -(const P &a,const P &b)
{
return {a.x-b.x,a.y-b.y};
}
P operator +(const P &a,const P &b)
{
return {a.x+b.x,a.y+b.y};
}
int T;
int sgn(int x)
{
return x<-0?-1:(x>0);
}
int det(P a,P b)
{
return a.x*b.y-a.y*b.x;
}
int dot(P a,P b)
{
return a.x*b.x+a.y*b.y;
}
int in_seg(P a,P b,P c)
{
return sgn(det(b-a,c-a))==0&&sgn(dot(a-c,b-c))<=0;
}
int segment_intersection(P a,P b,P c,P d)
{
if(sgn(det(b-a,c-a))*sgn(det(b-a,d-a))==-1&&sgn(det(d-c,a-c))*sgn(det(d-c,b-c))==-1)
return 1;
if(in_seg(a,b,d)||in_seg(a,b,c)||in_seg(c,d,a)||in_seg(c,d,b))
return 1;
return 0;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>T;
while(T--)
{
int n;
cin>>n;
// n=100;
vector<P>p(n);
for(auto &[x,y]:p)
{
// x=rand()%10000,y=rand()%10000;
// x*=2,y*=2;
cin>>x>>y;
}
if(n==1)
{
cout<<(int)1e8<<" "<<(int)1e8<<" "<<(int)1e8+1<<" "<<(int)1e8<<"\n";
continue;
}
sort(p.begin(),p.end(),[&](const P &a,const P &b){
if(a.y!=b.y)
return a.y<b.y;
return a.x>b.x;
});
int h=n/2;
P m=(p[h-1]+p[h]);
m.x/=2,m.y/=2;
vector<pair<P,P> >ans;
P A=m+P(1e8,0);
P B=m+P(-1e8,0);
P mab,mcd;
while(1)
{
mab=A,mcd=B;
mab.x+=rand()%L-L/2;
mab.y+=rand()%L-L/2;
mcd.x+=rand()%L-L/2;
mcd.y+=rand()%L-L/2;
int ok=1;
for(int i=0;i<n;i++)
{
if(in_seg(mab,mcd,p[i]))
{
ok=0;
break;
}
}
for(int i=0;i<h;i++)
{
if(!ok)
break;
for(int j=h;j<n;j++)
if(!segment_intersection(p[i],p[j],mab,mcd))
{
ok=0;
break;
}
}
if(ok)
break;
}
ans.push_back({mab,mcd});
random_shuffle(p.begin(),p.begin()+h);
random_shuffle(p.begin()+h,p.begin()+n);
// sort(p.begin(),p.begin()+h,[&](const P &a,const P &b){
// if(a.x!=b.x)
// return a.x<b.x;
// return a.y<b.y;
// });
// sort(p.begin()+h,p.begin()+n,[&](const P &a,const P &b){
// if(a.x!=b.x)
// return a.x<b.x;
// return a.y<b.y;
// });
// int u=0,v=h;
using pii=pair<int,int>;
deque<pii> q1,q2;
for(int i=0;i<h;i++)
for(int j=i+1;j<h;j++)
q1.push_back({i,j});
for(int i=h;i<n;i++)
for(int j=i+1;j<n;j++)
q2.push_back({i,j});
while(!q1.empty()&&!q2.empty())
{
while(q1.size())
{
auto [a,b]=q1.front();
int ok=0;
for(auto [u,v]:ans)
if(segment_intersection(p[a],p[b],u,v))
{
ok=1;
break;
}
if(ok)
q1.pop_front();
else
break;
}
while(q2.size())
{
auto [a,b]=q2.front();
int ok=0;
for(auto [u,v]:ans)
if(segment_intersection(p[a],p[b],u,v))
{
ok=1;
break;
}
if(ok)
q2.pop_front();
else
break;
}
if(!q1.size()||!q2.size())
break;
auto [ia,ib]=q1.front();
auto [ic,id]=q2.front();
q1.pop_front(),q2.pop_front();
P a=p[ia],b=p[ib],c=p[ic],d=p[id];
P mab=a+b;
mab.x/=2,mab.y/=2;
P mcd=c+d;
mcd.x/=2,mcd.y/=2;
P dir=a+b-c-d;
mab=mab+dir*50000;
mcd=mcd-dir*50000;
P A=mab,B=mcd;
int lim=10,ok=1;
while(lim--)
{
mab=A;
mcd=B;
mab.x+=rand()%L-L/2;
mcd.x+=rand()%L-L/2;
mab.y+=rand()%L-L/2;
mcd.y+=rand()%L-L/2;
ok=1;
for(int i=0;i<n;i++)
{
if(!ok)
break;
if(in_seg(mab,mcd,p[i]))
ok=0;
}
if(!segment_intersection(mab,mcd,a,b)||!segment_intersection(mab,mcd,c,d))
ok=0;
if(ok)
break;
}
if(!ok)
{
q1.push_back({ia,ib});
q2.push_front({ic,id});
}
else
ans.push_back({mab,mcd});
}
while(q1.size())
{
while(q1.size())
{
auto [a,b]=q1.front();
int ok=0;
for(auto [u,v]:ans)
if(segment_intersection(p[a],p[b],u,v))
{
ok=1;
break;
}
if(ok)
q1.pop_front();
else
break;
}
if(!q1.size())
break;
P a=p[q1.front().first],b=p[q1.front().second];
q1.pop_front();
P m=(a+b);
m.x/=2,m.y/=2;
P A=P(m.x,m.y+1e8),B=P(m.x,m.y-1e8);
P mab,mcd;
while(1)
{
mab=A;
mcd=B;
mab.x+=rand()%L-L/2;
mcd.x+=rand()%L-L/2;
mab.y+=rand()%L-L/2;
mcd.y+=rand()%L-L/2;
int ok=1;
for(int i=0;i<n;i++)
{
if(!ok)
break;
if(in_seg(mab,mcd,p[i]))
ok=0;
}
if(!segment_intersection(mab,mcd,a,b))
ok=0;
if(ok)
break;
}
ans.push_back({mab,mcd});
}
while(q2.size())
{
while(q2.size())
{
auto [a,b]=q2.front();
int ok=0;
for(auto [u,v]:ans)
if(segment_intersection(p[a],p[b],u,v))
{
ok=1;
break;
}
if(ok)
q2.pop_front();
else
break;
}
if(!q2.size())
break;
P a=p[q2.front().first],b=p[q2.front().second];
q2.pop_front();
P m=(a+b);
m.x/=2,m.y/=2;
P A=P(m.x,m.y+1e8),B=P(m.x,m.y-1e8);
P mab,mcd;
while(1)
{
mab=A;
mcd=B;
mab.x+=rand()%L-L/2;
mcd.x+=rand()%L-L/2;
mab.y+=rand()%L-L/2;
mcd.y+=rand()%L-L/2;
int ok=1;
for(int i=0;i<n;i++)
{
if(!ok)
break;
if(in_seg(mab,mcd,p[i]))
ok=0;
}
if(!segment_intersection(mab,mcd,a,b))
ok=0;
if(ok)
break;
}
ans.push_back({mab,mcd});
}
for(auto &[a,b]:ans)
{
cout<<a.x<<" "<<a.y<<" "<<b.x<<" "<<b.y<<"\n";
}
int z=1e8;
int tot=(n+1)/2;
while(ans.size()<tot)
{
cout<<(int)z<<" "<<(int)z<<" "<<(int)z+1<<" "<<(int)z<<"\n";
z++;
tot--;
}
// int ok=1;
// // ok&=ans.size()==(n+1)/2;
// for(int i=0;i<n;i++)
// {
// for(auto [u,v]:ans)
// {
// if(in_seg(u,v,p[i]))
// ok=0;
// }
// for(int j=i+1;j<n;j++)
// {
// int flag=0;
// for(auto [u,v]:ans)
// if(segment_intersection(p[i],p[j],u,v))
// flag=1;
// ok&=flag;
// }
// }
// cout<<ok<<endl;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3856kb
input:
2 3 0 0 2 1 4 0 4 0 1 1 0 2 1 1 2
output:
99999998 4 -99999995 -4 -1 100000005 3 -100000004 99999997 3 -99999995 -1 100001 -99998 -100002 100001
result:
ok 2 cases
Test #2:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
4 2 0 0 3 0 3 0 0 3 0 3 3 4 0 0 3 0 3 3 0 3 4 0 0 3 0 1 1 0 3
output:
99999997 4 -99999996 -4 99999999 4 -99999995 -4 3 99999996 -2 -100000004 100000003 1 -99999999 2 -1 -299998 2 300006 100000004 -3 -100000006 5 100004 -200002 -100003 200006
result:
ok 4 cases
Test #3:
score: 0
Accepted
time: 101ms
memory: 3644kb
input:
18093 1 -883 286 1 922 -705 3 614 -576 611 -576 607 -572 10 748 868 751 873 752 869 747 864 743 865 746 864 745 868 746 874 750 869 742 866 5 494 618 491 613 497 617 492 619 498 611 10 -639 -359 -634 -358 -642 -355 -638 -361 -638 -357 -634 -357 -641 -360 -639 -353 -633 -362 -642 -359 9 -327 -157 -32...
output:
100000000 100000000 100000001 100000000 100000000 100000000 100000001 100000000 100000608 -572 -99999385 -580 611 99999423 604 -100000577 100000742 870 -99999250 866 -249254 -499130 250750 500871 -849261 -349140 850747 350872 -349257 -499135 350755 500873 100749 -699138 -99258 700875 100000493 618 -...
result:
ok 18093 cases
Test #4:
score: 0
Accepted
time: 113ms
memory: 3612kb
input:
18174 9 398 -265 397 -261 399 -265 399 -267 404 -268 402 -269 400 -262 398 -266 401 -261 3 -128 -721 -128 -723 -127 -722 8 -28 62 -25 56 -30 61 -25 61 -30 55 -26 59 -24 57 -28 56 8 -91 -145 -88 -148 -92 -143 -88 -142 -91 -146 -93 -149 -93 -145 -94 -141 7 375 -521 370 -517 371 -519 370 -520 368 -516 ...
output:
100000392 -265 -99999604 -267 200405 -300264 -199605 299731 500402 -550263 -499605 549737 403 -500261 394 499737 405 99999743 396 -100000258 99999870 -725 -100000129 -720 -127 99999281 -128 -100000723 99999975 54 -100000023 61 -50032 -349950 49979 350058 349980 -349942 -350029 350055 -200027 -499950...
result:
ok 18174 cases
Test #5:
score: -100
Time Limit Exceeded
input:
18276 3 934 -359 916 -349 925 -349 9 -518 -436 -520 -428 -509 -430 -523 -432 -511 -417 -506 -427 -508 -420 -516 -432 -521 -426 1 762 -777 4 46 -219 32 -208 45 -215 43 -226 5 275 572 269 571 284 563 285 558 274 572 10 -196 886 -193 886 -187 888 -184 905 -198 890 -199 894 -203 888 -186 899 -186 900 -1...