QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#784523 | #692. Delete the Points | liuziqin | WA | 436ms | 134480kb | C++14 | 1.9kb | 2024-11-26 15:14:23 | 2024-11-26 15:14:25 |
Judging History
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=1;
while(T--)sol();
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3764kb
input:
4 1 1 2 2 5 5 6 6
output:
Yes 5.0000 5.0000 6.0000 6.0000 1.0000 1.0000 2.0000 2.0000
result:
ok OK
Test #2:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
4 0 0 1 2 2 1 4 4
output:
Yes 1.0000 1.0000 2.0000 2.0000 0.0000 0.0000 4.0000 4.0000
result:
ok OK
Test #3:
score: 0
Accepted
time: 0ms
memory: 3932kb
input:
4 1 2 3 2 2 1 2 3
output:
Yes 2.0000 2.0000 3.0000 3.0000 1.0000 1.0000 2.0000 2.0000
result:
ok OK
Test #4:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
6 12 9 1 5 10 14 20 14 15 4 7 9
output:
Yes 11.0000 4.0000 16.0000 9.0000 6.0000 9.0000 11.0000 14.0000 1.0000 0.0000 20.0000 19.0000
result:
ok OK
Test #5:
score: 0
Accepted
time: 0ms
memory: 4008kb
input:
10 39 72 59 52 23 17 2 31 30 0 25 88 2 36 61 23 4 96 59 76
output:
Yes -0.5000 31.0000 4.5000 36.0000 24.0000 72.0000 40.0000 88.0000 18.0000 0.0000 35.0000 17.0000 47.0000 52.0000 71.0000 76.0000 -4.0000 23.0000 69.0000 96.0000
result:
ok OK
Test #6:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
10 53 95 37 51 84 11 3 39 31 20 37 84 42 27 95 38 6 6 16 19
output:
Yes 31.0000 18.0000 42.0000 29.0000 4.5000 6.0000 17.5000 19.0000 37.0000 81.5000 53.0000 97.5000 76.0000 11.0000 103.0000 38.0000 3.0000 28.0000 37.0000 62.0000
result:
ok OK
Test #7:
score: -100
Wrong Answer
time: 436ms
memory: 134480kb
input:
3000 997371332 135791687 997371332 135791686 997371332 135791685 997371333 135791685 997371333 135791687 997371334 135791687 997371333 135791688 997371331 135791686 997371333 135791689 997371334 135791686 997371334 135791689 997371333 135791684 997371332 135791689 997371331 135791685 997371334 13579...
output:
No
result:
wrong answer The participant does not have a solution