QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #592460 | #7081. Cut the Plane | Afterlife | WA | 1114ms | 3704kb | C++14 | 9.3kb | 2024-09-26 22:42:40 | 2024-09-26 22:42:40 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e2+1e1+7,eps=0;
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<-eps?-1:(x>eps);
}
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;
int qwq=0;
while(T--)
{
++qwq;
int n;
cin>>n;
vector<P>p(n);
for(auto &[x,y]:p)
{
// x=rand()%1000,y=rand()%1000;
// 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()%10-5;
mab.y+=rand()%10-5;
mcd.x+=rand()%10-5;
mcd.y+=rand()%10-5;
if(1.0*clock()/CLOCKS_PER_SEC>1.8){
cout<<qwq<<endl;
return 0;
}
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});
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>;
queue<pii> q1,q2;
for(int i=0;i<h;i++)
for(int j=i+1;j<h;j++)
q1.push({i,j});
for(int i=h;i<n;i++)
for(int j=i+1;j<n;j++)
q2.push({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();
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();
else
break;
}
if(!q1.size()||!q2.size())
break;
auto [ia,ib]=q1.front();
auto [ic,id]=q2.front();
q1.pop(),q2.pop();
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;
while(1)
{
mab=A;
mcd=B;
mab.x+=rand()%10-5;
mcd.x+=rand()%10-5;
mab.y+=rand()%10-5;
mcd.y+=rand()%10-5;
if(1.0*clock()/CLOCKS_PER_SEC>1.8){
cout<<qwq<<endl;
return 0;
}
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)||!segment_intersection(mab,mcd,c,d))
ok=0;
if(ok)
break;
}
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();
else
break;
}
if(!q1.size())
break;
P a=p[q1.front().first],b=p[q1.front().second];
q1.pop();
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()%10-5;
mcd.x+=rand()%10-5;
mab.y+=rand()%10-5;
mcd.y+=rand()%10-5;
if(1.0*clock()/CLOCKS_PER_SEC>1.8){
cout<<qwq<<endl;
return 0;
}
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();
else
break;
}
if(!q2.size())
break;
P a=p[q2.front().first],b=p[q2.front().second];
q2.pop();
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()%6-3;
mcd.x+=rand()%6-3;
mab.y+=rand()%6-3;
mcd.y+=rand()%6-3;
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});
}
if(T<=5){
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: 3600kb
input:
2 3 0 0 2 1 4 0 4 0 1 1 0 2 1 1 2
output:
100000001 2 -99999994 -2 3 99999997 0 -100000000 100000005 3 -100000003 -1 100005 -100005 -99999 100002
result:
ok 2 cases
Test #2:
score: 0
Accepted
time: 0ms
memory: 3684kb
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:
100000004 -4 -100000002 4 100000000 2 -99999995 -2 3 99999998 0 -99999999 99999996 -3 -99999997 4 5 -300000 -3 300002 99999996 4 -99999999 -3 99997 -200000 -99996 200004
result:
ok 4 cases
Test #3:
score: -100
Wrong Answer
time: 1114ms
memory: 3704kb
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 100000000 100000000 100000001 100000000 100000000 100000000 100000001 100000000 100000000 100000000 100000001 100000000 100000000 100000000 100000001 100000000 100000000 100000000 100000001 100000000 100000000 100000000 ...
result:
wrong answer In case 3, there exist two lines are the same.