QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#1026 | #663584 | #21692. 【NOIP Round #3】移除石子 | max666dong123 | xiangqizhen | Failed. | 2024-10-21 18:02:28 | 2024-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)
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#663584 | #21692. 【NOIP Round #3】移除石子 | xiangqizhen | 100 ✓ | 111ms | 4020kb | C++14 | 2.9kb | 2024-10-21 16:19:30 | 2024-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
*/