QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#1031#663984#21692. 【NOIP Round #3】移除石子cleverpenguinyangjunhao2029Failed.2024-10-21 18:59:302024-10-21 18:59:30

Details

Extra Test:

Accepted
time: 0ms
memory: 3724kb

input:

1
2
0 0
0 1

output:

Yes
-1 0 0 1

result:

ok OK (1 test case)

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#663984#21692. 【NOIP Round #3】移除石子yangjunhao2029100 ✓64ms3744kbC++142.6kb2024-10-21 18:47:472024-10-21 18:47:47

answer

#include<bits/stdc++.h>
using namespace std;
int t,n;
struct node
{
	int x,y;
}s[3005],p[3005];
bool cmp(node x,node y)
{
	if(x.x==y.x)
	{
		return x.y<y.y;
	}
	return x.x<y.x;
}
signed main()
{
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>s[i].x>>s[i].y;
		}
		sort(s+1,s+1+n,cmp);
		s[0].x=-1;
		bool last=0;
		int lx=0,ly=0;
		cout<<"Yes\n";
		for(int i=1;i<=n;i++)
		{
			if(s[i].x!=s[i-1].x)
			{
				int now=0;
				for(int j=i;j<=n;j++)
				{
					if(s[j].x==s[i].x)
					{
						now++;
						p[now].x=s[j].x;
						p[now].y=s[j].y;
					}
					else
					{
						break;
					}
				}
				int k;
				for(k=1;k<=now-1;k+=2)
				{
					if(last!=0&&(p[k].y<=ly&&ly<p[k+1].y||p[k].y>=ly))
					{
						last=0;
						int bc=max(abs(p[k].x-lx),abs(p[k].y-ly));
						int xm=max(p[k].x,lx)-bc,ym=max(p[k].y,ly)-bc,xx=xm+bc,yx=ym+bc;
						cout<<xm<<' '<<ym<<' '<<xx<<' '<<yx<<'\n';
						k--;
					}
					else if(last!=0&&p[k].y<=ly&&ly==p[k+1].y)
					{
						if(abs(p[k].y-p[k+1].y)<=abs(p[k+1].x-lx))
						{
							int bc=max(abs(p[k+1].x-p[k].x),abs(p[k+1].y-p[k].y));
							int xm=max(p[k].x,p[k+1].x)-bc,ym=max(p[k].y,p[k+1].y)-bc,xx=xm+bc,yx=ym+bc;
							if(xm<0&&xm!=-1)
							{
								xm++;
							}
							if(xx<0&&xx!=-1)
							{
								xx++;
							}
							if(xm==-1&&xx==-1)
							{
								cout<<-0.5<<' '<<ym<<' '<<-0.5<<' '<<yx<<'\n';
							}
							else if(xm==-1)
							{
								cout<<-0.5<<' '<<ym<<' '<<xx<<".5 "<<yx<<'\n';
							}
							else if(xx==-1)
							{
								cout<<xm<<".5 "<<ym<<' '<<-0.5<<' '<<yx<<'\n';
							}
							else
							{
								cout<<xm<<".5 "<<ym<<' '<<xx<<".5 "<<yx<<'\n';
							}
						}
						else
						{
							last=0;
							swap(p[k].x,p[k+1].x);
							swap(p[k].y,p[k+1].y);
							int bc=max(abs(p[k].x-lx),abs(p[k].y-ly));
							int xm=max(p[k].x,lx)-bc,ym=max(p[k].y,ly)-bc,xx=xm+bc,yx=ym+bc;
							cout<<xm<<' '<<ym<<' '<<xx<<' '<<yx<<'\n';
							k--;
						}
					}
					else
					{
						int bc=max(abs(p[k+1].x-p[k].x),abs(p[k+1].y-p[k].y));
						int xm=max(p[k].x,p[k+1].x)-bc,ym=max(p[k].y,p[k+1].y)-bc,xx=xm+bc,yx=ym+bc;
						cout<<xm<<' '<<ym<<' '<<xx<<' '<<yx<<'\n';
					}
				}
				if(k==now&&last!=0)
				{
					last=0;
					int bc=max(abs(p[now].x-lx),abs(p[now].y-ly));
					int xm=max(p[now].x,lx)-bc,ym=max(p[now].y,ly)-bc,xx=xm+bc,yx=ym+bc;
					cout<<xm<<' '<<ym<<' '<<xx<<' '<<yx<<'\n';
				}
				else if(k==now)
				{
					last=1;
					lx=p[now].x;
					ly=p[now].y;
				}
			}
		}
	}
	return 0;
}