QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#784472#692. Delete the PointshysbzdkfWA 2ms3708kbC++143.2kb2024-11-26 15:06:532024-11-26 15:06:54

Judging History

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

  • [2024-11-26 15:06:54]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3708kb
  • [2024-11-26 15:06:53]
  • 提交

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<<"test1:"<<endl;
//					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=max(left+1,t.y-line_x);
						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<<"test2:"<<endl;
//					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=max(up+1,t.x-line_x);
						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: 3616kb

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: 3708kb

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: 0
Accepted
time: 0ms
memory: 3636kb

input:

6
12 9
1 5
10 14
20 14
15 4
7 9

output:

Yes
12 6 20 14
1 -9 15 5
5 9 10 14

result:

ok OK

Test #5:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

10
39 72
59 52
23 17
2 31
30 0
25 88
2 36
61 23
4 96
59 76

output:

Yes
39 52 59 72
2 10 23 31
-6 0 30 36
4 75 25 96
8 23 61 76

result:

ok OK

Test #6:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

10
53 95
37 51
84 11
3 39
31 20
37 84
42 27
95 38
6 6
16 19

output:

Yes
37 79 53 95
3 21 37 55
31 -33 84 20
42 -15 95 38
3 6 16 19

result:

ok OK

Test #7:

score: -100
Wrong Answer
time: 2ms
memory: 3672kb

input:

3000
997371332 135791687
997371332 135791686
997371332 135791685
997371333 135791685
997371333 135791687
997371334 135791687
997371333 135791688
997371331 135791686
997371333 135791689
997371334 135791686
997371334 135791689
997371333 135791684
997371332 135791689
997371331 135791685
997371334 13579...

output:

No

result:

wrong answer The participant does not have a solution