QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #592308 | #7081. Cut the Plane | Afterlife# | WA | 0ms | 3644kb | C++20 | 7.3kb | 2024-09-26 21:51:41 | 2024-09-26 21:51:42 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e2+1e1+7;
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;
vector<P>p(n);
for(auto &[x,y]:p)
{
// x=rand()%1000,y=rand()%1000;
// x*=2,y*=2;
cin>>x>>y,x*=2,y*=2;
}
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]);
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;
});
m.x/=2,m.y/=2;
vector<pair<P,P> >ans;
P A=m+P(1e8,0);
P B=m+P(-1e8,0);
if(p[h-1].y==p[h].y)
A.y+=5,B.y-=5;
ans.push_back({A,B});
// 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=mab-mcd;
mab=mab+dir*100000;
mcd=mcd-dir*100000;
mcd.x+=5;
mab.x-=5;
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);
A.x+=5;
B.x-=5;
ans.push_back({A,B});
}
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);
A.x+=5;
B.x-=5;
ans.push_back({A,B});
}
// while(u+1<=h-1&&v+1<=n-1)
// {
// P a=p[u],b=p[u+1];
// P c=p[v],d=p[v+1];
// P mab=a+b;
// mab.x/=2,mab.y/=2;
// P mcd=c+d;
// mcd.x/=2,mcd.y/=2;
// P dir=mab-mcd;
// mab=mab+dir*100000;
// mcd=mcd-dir*100000;
// mcd.x+=5;
// mab.x-=5;
// ans.push_back({mab,mcd});
// u++,v++;
// }
// if(n&1)
// {
// P a=p[v],b=p[v+1];
// 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);
// A.x+=5;
// B.x-=5;
// ans.push_back({A,B});
// }
auto cdiv=[&](int x,int y)
{
if(x>=0)
return (x+y-1)/y;
else
return -((-x)/y);
};
auto fdiv=[&](int x,int y)
{
if(x>=0)
return x/y;
else
return -(((-x)+y-1)/y);
};
for(auto [a,b]:ans)
{
// a.x/=2;
// a.y/=2;
// b.x/=2;
// b.y/=2;
a.x=cdiv(a.x,2);
a.y=cdiv(a.y,2);
b.x=fdiv(b.x,2);
b.y=fdiv(b.y,2);
cout<<a.x<<" "<<a.y<<" "<<b.x<<" "<<b.y<<"\n";
}
// int ok=1;
// 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;
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3544kb
input:
2 3 0 0 2 1 4 0 4 0 1 1 0 2 1 1 2
output:
50000002 3 -49999998 -3 4 50000001 -2 -50000000 50000001 4 -49999999 -2 99999 -99999 -99997 100001
result:
ok 2 cases
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3644kb
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:
50000002 3 -49999999 -3 50000002 3 -49999999 -3 4 50000002 -1 -49999999 50000002 2 -49999999 1 -1 -300000 4 300003 50000001 1 -50000000 0 99999 -200000 -99997 200002
result:
wrong answer In case 4, there exists a line passing through some given points.