QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#784499 | #692. Delete the Points | liuziqin | RE | 0ms | 0kb | C++14 | 1.9kb | 2024-11-26 15:10:42 | 2024-11-26 15:10:42 |
answer
#include<bits/stdc++.h>
using namespace std;
const int N=3005;
const int INF=1e9;
struct node{
int ix,iy;
double len;
};
bool operator<(node a,node b){
return a.len<b.len;
}
bool operator >(node a,node b){
return a.len>=b.len;
}
double step[N][4];
bool used[N];
int n;
struct line{
int x,y;
}a[N];
bool cmp(line a,line b){
if(a.x==b.x)return a.y<b.y;
return a.x<b.x;
}
bool check(){
memset(used,0,sizeof(used));
for(int i=1;i<=n/2;i++){
int cnt=0;
for(int j=1;j<=n;j++){
if(used[j])continue;
double x=a[j].x,y=a[j].y;
if(step[i][1]<=x&&x<=step[i][3]&&step[i][2]<=y&&y<=step[i][4]){
cnt++;
used[j]=1;
}
}
if(cnt!=2){
return 0;
}
}
return 1;
}
void sol(){
priority_queue<node,vector<node>,greater<node> >q;
set<int>s;
memset(used,0,sizeof(used));
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
q.push({i,j,(double)max(abs(a[i].x-a[j].x),abs(a[i].y-a[j].y))});
for(int i=1;i<=n/2;i++){
while(!q.empty()){
node t=q.top();
q.pop();
if(used[t.ix]||used[t.iy])continue;
used[t.ix]=used[t.iy]=1;
int s1=t.ix,s2=t.iy;
step[i][1]=min(a[s1].x,a[s2].x);
step[i][2]=min(a[s1].y,a[s2].y);
step[i][3]=max(a[s1].x,a[s2].x);
step[i][4]=max(a[s1].y,a[s2].y);
double t1=abs(int(a[s1].x-a[s2].x)),t2=abs(int(a[s1].y-a[s2].y));
if(t1<t2){
step[i][1]-=(t2-t1)/2.0;
step[i][3]+=(t2-t1)/2.0;
}
else {
step[i][2]-=(t1-t2)/2.0;
step[i][4]+=(t1-t2)/2.0;
}
break;
}
}
if(check()){
cout<<"Yes\n";
for(int i=1;i<=n/2;i++)cout<<fixed<<setprecision(4)<<step[i][1]<<" "<<step[i][2]<<" "<<step[i][3]<<" "<<step[i][4]<<"\n";
}
else cout<<"No\n";
}
int main(){
freopen("stone.in","r",stdin);
freopen("stone.out","w",stdout);
int T;
cin>>T;
while(T--)sol();
}
详细
Test #1:
score: 0
Dangerous Syscalls
input:
4 1 1 2 2 5 5 6 6