QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#784523#692. Delete the PointsliuziqinWA 436ms134480kbC++141.9kb2024-11-26 15:14:232024-11-26 15:14:25

Judging History

This is the latest submission verdict.

  • [2024-11-26 15:14:25]
  • Judged
  • Verdict: WA
  • Time: 436ms
  • Memory: 134480kb
  • [2024-11-26 15:14:23]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
const int N=3005;
const int INF=1e9;
struct node{
	int ix,iy;
	double len;
};
bool operator<(node a,node b){
	return a.len<b.len;
}
bool operator >(node a,node b){
	return a.len>=b.len;
}
double step[N][4];
bool used[N];
int n;
struct line{
	int x,y;
}a[N];
bool cmp(line a,line b){
	if(a.x==b.x)return a.y<b.y;
	return a.x<b.x;
}
bool check(){
	memset(used,0,sizeof(used));
	for(int i=1;i<=n/2;i++){
		int cnt=0;
		for(int j=1;j<=n;j++){
			if(used[j])continue;
			double x=a[j].x,y=a[j].y;
			if(step[i][1]<=x&&x<=step[i][3]&&step[i][2]<=y&&y<=step[i][4]){
				cnt++;
				used[j]=1;
			}
		}
		if(cnt!=2){
			return 0;
		}
	}
	return 1;
}
void sol(){
	priority_queue<node,vector<node>,greater<node> >q;
	set<int>s;
	memset(used,0,sizeof(used));
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
	for(int j=i+1;j<=n;j++)
	q.push({i,j,(double)max(abs(a[i].x-a[j].x),abs(a[i].y-a[j].y))});
	for(int i=1;i<=n/2;i++){
		while(!q.empty()){
			node t=q.top();
			q.pop();
			if(used[t.ix]||used[t.iy])continue;
			used[t.ix]=used[t.iy]=1;
			int s1=t.ix,s2=t.iy;
			step[i][1]=min(a[s1].x,a[s2].x);
			step[i][2]=min(a[s1].y,a[s2].y);
			step[i][3]=max(a[s1].x,a[s2].x);
			step[i][4]=max(a[s1].y,a[s2].y);
			double t1=abs(int(a[s1].x-a[s2].x)),t2=abs(int(a[s1].y-a[s2].y));
			if(t1<t2){
				step[i][1]-=(t2-t1)/2.0;
				step[i][3]+=(t2-t1)/2.0;
			}
			else {
				step[i][2]-=(t1-t2)/2.0;
				step[i][4]+=(t1-t2)/2.0;
			}
			break;
		}
	}
	if(check()){
		cout<<"Yes\n";
		for(int i=1;i<=n/2;i++)cout<<fixed<<setprecision(4)<<step[i][1]<<" "<<step[i][2]<<" "<<step[i][3]<<" "<<step[i][4]<<"\n";
	}
	else cout<<"No\n";
}
int main(){
//	freopen("stone.in","r",stdin);
//	freopen("stone.out","w",stdout);
	int T=1;
	while(T--)sol();
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3764kb

input:

4
1 1
2 2
5 5
6 6

output:

Yes
5.0000 5.0000 6.0000 6.0000
1.0000 1.0000 2.0000 2.0000

result:

ok OK

Test #2:

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

input:

4
0 0
1 2
2 1
4 4

output:

Yes
1.0000 1.0000 2.0000 2.0000
0.0000 0.0000 4.0000 4.0000

result:

ok OK

Test #3:

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

input:

4
1 2
3 2
2 1
2 3

output:

Yes
2.0000 2.0000 3.0000 3.0000
1.0000 1.0000 2.0000 2.0000

result:

ok OK

Test #4:

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

input:

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

output:

Yes
11.0000 4.0000 16.0000 9.0000
6.0000 9.0000 11.0000 14.0000
1.0000 0.0000 20.0000 19.0000

result:

ok OK

Test #5:

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

input:

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

output:

Yes
-0.5000 31.0000 4.5000 36.0000
24.0000 72.0000 40.0000 88.0000
18.0000 0.0000 35.0000 17.0000
47.0000 52.0000 71.0000 76.0000
-4.0000 23.0000 69.0000 96.0000

result:

ok OK

Test #6:

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

input:

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

output:

Yes
31.0000 18.0000 42.0000 29.0000
4.5000 6.0000 17.5000 19.0000
37.0000 81.5000 53.0000 97.5000
76.0000 11.0000 103.0000 38.0000
3.0000 28.0000 37.0000 62.0000

result:

ok OK

Test #7:

score: -100
Wrong Answer
time: 436ms
memory: 134480kb

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