QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#1023#663130#21692. 【NOIP Round #3】移除石子mayikemayikeFailed.2024-10-21 13:37:102024-10-21 13:37:10

Details

Extra Test:

Invalid Input

input:

1
4
1 0
1 2
-1 2
5 2

output:


result:

FAIL Integer parameter [name=x] equals to -1, violates the range [0, 10^9] (stdin, line 5)

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#663130#21692. 【NOIP Round #3】移除石子mayike100 ✓86ms4492kbC++142.0kb2024-10-21 13:34:322024-10-21 13:34:32

answer

#include<bits/stdc++.h>
using namespace std;
using pi=pair<int,int>;
const int N=3005;
int T,n,b[N],Ans;
struct no{
	int x,y;
}a[N];
struct an{
	double x,y,s,t;
}ans[N];
set<pi>st[N];
queue<int>q;
void tg(int j,int k){
	int s=max(a[j].x,a[k].x),t=b[a[j].y],z=max(b[a[j].y]-b[a[k].y],abs(a[j].x-a[k].x));
	ans[++Ans]={1.0*(s-z),1.0*(t-z),1.0*max(a[j].x,a[k].x),1.0*b[a[j].y]};
}
int main(){
//	freopen("stone.in","r",stdin);
//	freopen("stone.out","w",stdout);
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%d%d",&a[i].x,&a[i].y);
			b[i]=a[i].y;
		}
		sort(b+1,b+1+n);
		int m=unique(b+1,b+1+n)-b-1;
		for(int i=1;i<=n;i++){
			a[i].y=lower_bound(b+1,b+1+m,a[i].y)-b;
			st[a[i].y].insert({a[i].x,i});
		}
		bool fg=1;
		for(int i=1;i<=m&&fg;i++){
			while(st[i].size()>0){
				int j=(*st[i].begin()).second;
				st[i].erase({a[j].x,j});
				if(st[i].size()==0){
					if(q.empty())q.push(j);
					else{
						int k=q.front();
						q.pop();
						tg(j,k);
					}
				}
				else{
					int k=(*st[i].begin()).second;
					if(!q.empty()&&a[j].x<=a[q.front()].x&&a[q.front()].x<=a[k].x){
						if(a[q.front()].x==a[k].x){
							int p=q.front();
							if(a[k].x-a[j].x==b[a[k].y]-b[a[p].y]){
								tg(k,p);
								q.pop();
								st[i].insert({a[j].x,j});
								st[i].erase({a[k].x,k});
								ans[Ans].x+=0.5;
								ans[Ans].s+=0.5;
							}
							else if(a[k].x-a[j].x<b[a[k].y]-b[a[p].y]){
								tg(j,k);
								st[i].erase({a[k].x,k});
							}
							else{
								tg(k,p);
								q.pop();
								st[i].insert({a[j].x,j});
								st[i].erase({a[k].x,k});
							}
						}
						else{
							tg(j,q.front());
							q.pop();
						}
					}
					else{
						tg(j,k);
						st[i].erase({a[k].x,k});
					}
				}
			}
		}
		printf("Yes\n");
		for(int i=1;i<=Ans;i++)printf("%.4lf %.4lf %.4lf %.4lf\n",ans[i].x,ans[i].y,ans[i].s,ans[i].t);
		for(int i=1;i<=m;i++)st[i].clear();
		Ans=0;
		while(!q.empty())q.pop();
	}
	return 0;
}