QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#784376#692. Delete the PointshysbzdkfWA 0ms3692kbC++143.1kb2024-11-26 14:50:182024-11-26 14:50:18

Judging History

你现在查看的是最新测评结果

  • [2024-11-26 14:50:18]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3692kb
  • [2024-11-26 14:50:18]
  • 提交

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