QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#592096 | #7081. Cut the Plane | Afterlife# | WA | 0ms | 3876kb | C++20 | 1.9kb | 2024-09-26 20:41:18 | 2024-09-26 20:41:18 |
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;
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)
cin>>x>>y,x*=2,y*=2;
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);
if(p[h-1].y==p[h].y)
A.y+=5,B.y-=5;
ans.push_back({A,B});
int u=0,v=h;
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,1e8),B=P(m.x,-1e8);
A.x+=5;
B.x-=5;
ans.push_back({A,B});
}
for(auto [a,b]:ans)
{
a.x/=2;
a.y/=2;
b.x/=2;
b.y/=2;
cout<<a.x<<" "<<a.y<<" "<<b.x<<" "<<b.y<<"\n";
}
}
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3876kb
input:
2 3 0 0 2 1 4 0 4 0 1 1 0 2 1 1 2
output:
50000002 2 -49999998 -2 5 50000000 0 -50000000 50000001 3 -49999999 -1 -100002 -99999 100004 100001
result:
wrong answer In case 1, there exist two points lie in the same piece.