QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#784376 | #692. Delete the Points | hysbzdkf | WA | 0ms | 3692kb | C++14 | 3.1kb | 2024-11-26 14:50:18 | 2024-11-26 14:50:18 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,n;
struct node{
int x,y;
}a[3001];
node q1[11];
bool flag1[11],ans_flag;
void solve1(int dep){
// cout<<"__________"<<dep<<"_________"<<endl;
if(dep==n){
cout<<"Yes"<<endl;
for(int i=1;i<=n/2;i++){
cout<<q1[i*2-1].x<<" "<<q1[i*2-1].y<<" ";
cout<<q1[i*2].x<<" "<<q1[i*2].y<<endl;
}
ans_flag=1;
return ;
}
for(int i=1;i<=n;i++){
if(flag1[i])continue;
for(int j=i+1;j<=n;j++){
if(flag1[j])continue;
node s={min(a[i].x,a[j].x),min(a[i].y,a[j].y)};
node t={max(a[i].x,a[j].x),max(a[i].y,a[j].y)};
int line_x=t.x-s.x,line_y=t.y-s.y;
bool cp_flag=1;
for(int k=1;k<=n;k++){
if(flag1[k]||k==i||k==j)continue;
if(a[k].x>=s.x&&a[k].x<=t.x&&a[k].y>=s.y&&a[k].y<=t.y)cp_flag=0;
}
if(cp_flag){
// cout<<s.x<<" "<<s.y<<" "<<t.x<<" "<<t.y<<endl;
// cout<<114514<<endl;
if(line_x>line_y){
int left=0,right=1e18;
for(int k=1;k<=n;k++){
if(flag1[k]||k==i||k==j)continue;
if(a[k].x<s.x||a[k].x>t.x)continue;
if(a[k].y<t.y)left=max(left,a[k].y);
if(a[k].y>s.y)right=min(right,a[k].y);
}
// cout<<"l&r:"<<left<<" "<<right<<endl;
if(left==0||right==1e18||right-left-2>=line_x){
q1[dep+1].x=s.x;
if(left==0)q1[dep+1].y=t.y-line_x;
else q1[dep+1].y=left+1;
q1[dep+2].x=t.x;
q1[dep+2].y=q1[dep+1].y+line_x;
flag1[i]=1;
flag1[j]=1;
solve1(dep+2);
flag1[i]=0;
flag1[j]=0;
if(ans_flag)return ;
// cout<<"right"<<endl;
}
}
else{
int up=0,down=1e18;
for(int k=1;k<=n;k++){
if(flag1[k]||k==i||k==j)continue;
if(a[k].y<s.y||a[k].y>t.y)continue;
if(a[k].x<t.x)up=max(up,a[k].x);
if(a[k].x>s.x)down=min(up,a[k].x);
}
// cout<<"u&d:"<<up<<" "<<down<<endl;
if(up==0||down==1e18||down-up-2>=line_y){
q1[dep+1].y=s.y;
if(up==0)q1[dep+1].x=t.x-line_y;
else q1[dep+1].x=up+1;
q1[dep+2].y=t.y;
q1[dep+2].x=q1[dep+1].x+line_y;
flag1[i]=1;
flag1[j]=1;
solve1(dep+2);
flag1[i]=0;
flag1[j]=0;
if(ans_flag)return ;
// cout<<"right"<<endl;
}
}
}
}
}
}
void solve2(){
ans_flag=1;
cout<<"Yes"<<endl;
for(int i=1;i<=n/2;i++){
cout<<a[i*2-1].x<<" "<<a[i*2-1].y<<" ";
cout<<a[i*2].x<<" "<<a[i*2].y<<endl;
}
}
bool cmp(node x,node y){
return x.y<y.y;
}
void solve3(){
ans_flag=1;
sort(a+1,a+1+n,cmp);
cout<<"Yes"<<endl;
for(int i=1;i<=n/2;i++){
cout<<a[i*2-1].x<<" "<<a[i*2-1].y<<" ";
int dt=a[i*2].y-a[i*2-1].y;
cout<<dt<<" "<<a[i*2].y<<endl;
}
}
signed main(){
// freopen("stone.in","r",stdin);
// freopen("stone.out","w",stdout);
// cin>>T;
// while(T--){
cin>>n;
bool flag2=1,flag3=1;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].y;
if(a[i].x!=2*i||a[i].y!=2*i)flag2=0;
if(a[i].x!=0)flag3=0;
}
if(n<=10)solve1(0);
else{
if(flag2)solve2();
else{
if(flag3)solve3();
}
}
if(!ans_flag)
cout<<"No"<<endl;
// }
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3640kb
input:
4 1 1 2 2 5 5 6 6
output:
Yes 1 1 2 2 5 5 6 6
result:
ok OK
Test #2:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
4 0 0 1 2 2 1 4 4
output:
Yes -1 0 1 2 1 1 4 4
result:
ok OK
Test #3:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
4 1 2 3 2 2 1 2 3
output:
Yes 1 1 2 2 2 2 3 3
result:
ok OK
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3628kb
input:
6 12 9 1 5 10 14 20 14 15 4 7 9
output:
Yes 12 5 20 13 1 -9 15 5 5 9 10 14
result:
wrong answer We have 1 point(s) in query 0