QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#1026#663584#21692. 【NOIP Round #3】移除石子max666dong123xiangqizhenFailed.2024-10-21 18:02:282024-10-21 18:02:28

Details

Extra Test:

Accepted
time: 0ms
memory: 3872kb

input:

1
10
2 1
1 3
3 3
2 5
3 5
4 3
1 4
5 2
5 1
3 1

output:

YES
0.5 4.0 1.5 3.0
-1.5 5.0 2.5 1.0
1.5 5.0 3.5 3.0
2.5 3.0 4.5 1.0
4.5 2.0 5.5 1.0

result:

ok OK (1 test case)

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#663584#21692. 【NOIP Round #3】移除石子xiangqizhen100 ✓111ms4020kbC++142.9kb2024-10-21 16:19:302024-10-21 16:19:30

answer

#include<bits/stdc++.h>
#define int long long
#define f(i,j,n) for(long long i=j;i<=n;i++)
#define updmax(a,b) a=max(a,b)
#define updmin(a,b) a=min(a,b)
#define pb push_back
//#define XQZ
//#define NXD
using namespace std;
const int N=3010;
int n;
struct abc{
	int x,y;
}c[N];
bool bh(int up,int down,int lft,int rght,int x,int y){
	return (x>=lft&&x<=rght&&y>=down&&y<=up);
}
pair<pair<double,double>,pair<double,double> >ans[N];
map<int,int> mp;
bool vis[N];
void gs(){
	cin>>n;
	f(i,1,n){
		cin>>c[i].x>>c[i].y;
	}
	sort(c+1,c+1+n,[&](abc a,abc b){return a.x<b.x||(a.x==b.x&&a.y>b.y);});
	int cnt=0,ud=0,upp=0;
	f(i,1,n){
//		cout<<i<<":"<<upp<<endl;
//		if(c[i].x!=c[i+1].x||i+1>n){up=i;continue;}
		double rght=max(c[i].x,c[i+1].x);
		int down=min(c[i].y,c[i+1].y);
		int ys=max(abs(c[i].x-c[i+1].x),abs(c[i].y-c[i+1].y));
		int up=down+ys;
		double lft=rght-ys;
		if((lft!=min(c[i].x,c[i+1].x))){
			lft=lft+0.5;
			rght=rght+0.5;
		}
		bool tg=0;
		f(j,i+2,min(n,i+2))tg|=bh(up,down,lft,rght,c[j].x,c[j].y);
		if(upp)f(j,upp,upp)tg|=bh(up,down,lft,rght,c[j].x,c[j].y);
		if(i+1>n)tg=1;
		if(tg){
			if(upp&&c[upp].y==c[i+1].y){
				double rght=max(c[i+1].x,c[upp].x);
				double down=min(c[i+1].y,c[upp].y);
				double ys=max(abs(c[i+1].x-c[upp].x),abs(c[i+1].y-c[upp].y));
				double up=down+ys;int lft=rght-ys;
				if((up!=max(c[i+1].y,c[upp].y))){
					up=up-0.5;
					down=down-0.5;
				}
				ans[++ud]={{lft,rght},{up,down}};
				upp=i;
				i++;
			}else if(upp){
				double rght=max(c[i].x,c[upp].x);
				double down=min(c[i].y,c[upp].y);
				double ys=max(abs(c[i].x-c[upp].x),abs(c[i].y-c[upp].y));
				double up=down+ys;int lft=rght-ys;
				if((up!=max(c[i].y,c[upp].y))){
					up=up-0.5;
					down=down-0.5;
				}
				ans[++ud]={{lft,rght},{up,down}};
				upp=0;
			}else upp=i;continue;
//			c[++cnt]=c[i];continue;
		}else 
//			ans[++ud]={{lft*1.0+0.5,rght*1.0+0.5},{up,down}};
			ans[++ud]={{lft,rght},{up,down}};
		i++;
	}
//	f(i,1,cnt){
//		int rght=max(c[i].x,c[i+1].x);
//		int down=min(c[i].y,c[i+1].y);
//		int ys=max(abs(c[i].x-c[i+1].x),abs(c[i].y-c[i+1].y));
//		int up=down+ys,lft=rght-ys;
////		if(i+2<=n&&bh(up,down,lft,rght,c[i+2].x,c[i+2].y)){
////			cout<<"NO\n";return;
////		}else 
//		ans[++ud]={{lft,rght},{up,down}};
//		i++;
//	}
	cout<<"YES\n";
	f(i,1,ud){
		printf("%.1lf %.1lf %.1lf %.1lf\n",ans[i].first.first,ans[i].second.first,ans[i].first.second,ans[i].second.second);
//		printf("Polygon\n%.1lf %.1lf\n%.1lf %.1lf\n%.1lf %.1lf\n%.1lf %.1lf\n...\n",ans[i].first.first,ans[i].second.first,ans[i].first.first,ans[i].second.second,ans[i].first.second,ans[i].second.second,ans[i].first.second,ans[i].second.first);
	}
}
signed main(){
//#ifndef XQZ
//	freopen("stone.in","r",stdin);
//	freopen("stone.out","w",stdout);
//#endif
//#ifdef NXD
	int t=0;cin>>t;while(t--)
//#endif
		gs();
	return 0;
}
/*
1
4
0 2
2 2
2 -1
3 5
*/