QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#141607 | #5251. Constellations | PhantomThreshold# | WA | 3029ms | 128532kb | C++20 | 2.0kb | 2023-08-17 17:50:27 | 2023-08-17 17:50:35 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const double eps=1e-6;
typedef __int128 ll;
struct frac{
double p;
inline frac(){p=0;}
inline frac(ll x){p=x;}
frac operator + (const frac &x)const{return p+x.p;}
frac operator - (const frac &x)const{return p-x.p;}
frac operator * (const frac &x)const{return p*x.p;}
frac operator / (const frac &x)const{return p/x.p;}
bool operator < (const frac &x)const{return p<x.p-eps;}
};
struct point{
frac x,y;
point operator + (const point &k)const{return (point){x+k.x,y+k.y};}
point operator - (const point &k)const{return (point){x-k.x,y-k.y};}
point operator * (const frac &k)const{return (point){x*k,y*k};}
point operator / (const frac &k)const{return (point){x/k,y/k};}
frac abs2()const{return x*x+y*y;}
frac dis2(const point &k)const{return ((*this)-k).abs2();}
};
const int maxn=6000;
int n;
point a[maxn+50];
int sz[maxn+50];
int main(){
ios_base::sync_with_stdio(false);
cin >> n;
for (int i=1;i<=n;i++){
int x,y;
cin >> x >> y;
a[i]=(point){frac(x),frac(y)};
}
set<tuple<frac,int,int>> s;
for (int i=1;i<=n;i++) sz[i]=1;
int id=n;
for (int i=1;i<=n;i++){
for (int j=i+1;j<=n;j++){
s.emplace(a[i].dis2(a[j]),i,j);
}
}
for (;;){
if (s.empty()) break;
auto tmp=*(s.begin());
int x=get<1>(tmp);
int y=get<2>(tmp);
sz[++id]=sz[x]+sz[y];
a[id]=(a[x]*sz[x]+a[y]*sz[y])/(sz[x]+sz[y]);
// cerr << "merge : " << id << " " << x << " " << y << " " << sz[x] << " " << sz[y] << endl;
for (int i=1;i<id;i++) if (sz[i]!=0){
int l=i,r=x;
if (l>r) swap(l,r);
if (l==r) continue;
auto it=s.find(make_tuple(a[l].dis2(a[r]),l,r));
if (it!=s.end()) s.erase(it);
}
sz[x]=0;
for (int i=1;i<id;i++) if (sz[i]!=0){
int l=i,r=y;
if (l>r) swap(l,r);
if (l==r) continue;
auto it=s.find(make_tuple(a[l].dis2(a[r]),l,r));
if (it!=s.end()) s.erase(it);
}
sz[y]=0;
for (int i=1;i<id;i++) if (sz[i]!=0){
s.emplace(a[i].dis2(a[id]),i,id);
}
cout << sz[id] << "\n";
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3560kb
input:
2 0 0 1 0
output:
2
result:
ok single line: '2'
Test #2:
score: -100
Wrong Answer
time: 3029ms
memory: 128532kb
input:
2000 1000 -1000 1000 -999 1000 -998 1000 -997 1000 -996 1000 -995 1000 -994 1000 -993 1000 -992 1000 -991 1000 -990 1000 -989 1000 -988 1000 -987 1000 -986 1000 -985 1000 -984 1000 -983 1000 -982 1000 -981 1000 -980 1000 -979 1000 -978 1000 -977 1000 -976 1000 -975 1000 -974 1000 -973 1000 -972 1000...
output:
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...
result:
wrong answer 1500th lines differ - expected: '4', found: '6'