QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#784499#692. Delete the PointsliuziqinRE 0ms0kbC++141.9kb2024-11-26 15:10:422024-11-26 15:10:42

Judging History

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

  • [2024-11-26 15:10:42]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-11-26 15:10:42]
  • 提交

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;
	cin>>T;
	while(T--)sol();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Dangerous Syscalls

input:

4
1 1
2 2
5 5
6 6

output:


result: