QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#389334#692. Delete the Pointsdingdingtang11514TL 0ms0kbC++142.6kb2024-04-14 09:46:322024-04-14 09:46:34

Judging History

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

  • [2024-04-14 09:46:34]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-04-14 09:46:32]
  • 提交

answer

#include <iostream>
#include <cstring> 
#include <map>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
// #include <map>
// #include <bits/stdc++.h>

// #define int long long
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rof(i,a,b) for(int i=(a);i>=(b);i--)
#define Grf(it,u,to) for(int it=he[u],to;to=e[it],it;it=nxt[it]) 
#define In __inline 
#define OP operator
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
namespace Mine {
	// mt19937_64 wql(514);
	In int read() {
		int x=1,a=0;
		char ch=getchar();
		while(ch>'9' || ch<'0') x=(ch=='-')?-1:x,ch=getchar();
		while(ch>='0' && ch<='9') a=(a<<1)+(a<<3)+(ch-'0'),ch=getchar();
		return a*x;
	}const int N=6005;
typedef pair<int,int> pii;
#define x first
#define y second
	pii a[N];int n,l[N],r[N];
	void del(int u){l[r[u]]=l[u],r[l[u]]=r[u];}
	pair<double,double> ans1[N],ans2[N];
	void solve() {
		n=read()/2; For(i,1,n*2) {int x=read(),y=read();a[i]={x,y};}
		For(i,0,n*2+1) l[i]=i-1,r[i]=i+1;
		sort(a+1,a+1+n*2) ;
		// For(i,1,n*2) printf("%d %d\n",a[i].x,a[i].y);
		int cnt=0;Rof(i,n,1) {
			int px=l[n*2+1],py=l[px],pz=l[py];
			pii x=a[px],y=a[py],z=a[pz];
			// printf("%d %d %d\n",px,a[px].x,x.y);
			if(i==1) ans1[i]={min(x.x,y.x)-1,min(x.y,y.y)-1},ans2[i]={min(x.x,y.x)+1e9,min(x.y,y.y)+1e9};
			else {
				if(x.x==y.x) ans1[i]=x,ans2[i]={x.x+x.y-y.y,y.y},del(px),del(py);
				else {
					if(x.y>=y.y) ans1[i]=y,ans2[i]={y.x+1e9,y.y+1e9},del(px),del(py);
					else {
						if(z.x==y.x&&z.y>x.y) {
							ans1[i]=y,ans2[i]={z.x+y.y-z.y,z.y};del(py);del(pz);
						}else {
							if(z.x==y.x&&z.y==x.y) {
								if(y.y-z.y<=x.x-z.x) {
									int len=y.y-z.y;
									ans1[i]={y.x-0.5,y.y},ans2[i]={y.x-0.5+len,y.y-len};
									del(py);del(pz);
								}else{
									int len=x.x-z.x;
									ans1[i]={z.x,z.y-0.5},ans2[i]={z.x+len,z.y-0.5+len};
									del(px);del(pz);
								}
							}else {
								ans1[i]={x.y,y.x},ans2[i]={x.y+1e9,y.x+1e9};
								del(px);del(py);
							}
						}
					}
					// if(y.first!=z.first||z.second>x.second) ans1[i]=x,ans2[i]=y,del(px),del(py);
					// else 
					// if(x.second>=y.second) ans1[i]=x,ans2[i]=y,del(px),del(py);
					// else {
						// if(z.first!=y.first||z.second<x.second)
					// }
				}
			}
			
		}puts("Yes");
		Rof(i,n,1) printf("%lf %lf %lf %lf\n",ans1[i].x,ans1[i].y,ans2[i].x,ans2[i].y);
	}signed main() {
		int _=read();while(_--)solve();
		return 0;
	}
}signed main() {
	// freopen("homework.in","r",stdin);
	// freopen("homework.out","w",stdout);
	return Mine::main();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

4
1 1
2 2
5 5
6 6

output:


result: