QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#74025 | #5251. Constellations | ricky0129 | WA | 3547ms | 128780kb | C++17 | 4.5kb | 2023-01-30 10:59:30 | 2023-01-30 10:59:32 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vll vector<ll>
#define FOR(i,n) for(int i=0;i<n;i++)
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define f first
#define s second
const int MOD = (int)1e9+7;
template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
typedef Point P;
T x, y;
explicit Point(T x=0, T y=0) : x(x), y(y) {}
bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
P operator+(P p) const { return P(x+p.x, y+p.y); }
P operator-(P p) const { return P(x-p.x, y-p.y); }
P operator*(T d) const { return P(x*d, y*d); }
P operator/(T d) const { return P(x/d, y/d); }
T dot(P p) const { return x*p.x + y*p.y; }
T cross(P p) const { return x*p.y - y*p.x; }
T cross(P a, P b) const { return (a-*this).cross(b-*this); }
T dist2() const { return x*x + y*y; }
double dist() const { return sqrt((double)dist2()); }
// angle to x-axis in interval [-pi, pi]
double angle() const { return atan2(y, x); }
P unit() const { return *this/dist(); } // makes dist()=1
P perp() const { return P(-y, x); } // rotates +90 degrees
P normal() const { return perp().unit(); }
// returns point rotated 'a' radians ccw around the origin
P rotate(double a) const {
return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
friend ostream& operator<<(ostream& os, P p) {
return os << "(" << p.x << "," << p.y << ")"; }
};
typedef Point<double> P;
struct star{
ll cc=1; P center;
ll ss1=0,ss2=0;
ll s1 =0 ,s2=0;
star(){};
star(P c){
center = c;
ss1 = c.x*c.x;
ss2 = c.y*c.y;
s1 = c.x;
s2 = c.y;
cc = 1;
}
double dist(star& other){
ll sum = ss1*other.cc+ss2*other.cc;
sum+=other.ss1*cc+other.ss2*cc;
sum-=2*(s1)*other.s1+2*s2*other.s2;
//assert(sum%(cc+other.cc)==0);
return sum/(double)(cc+other.cc);
}
void merge(star& other){
ss1+=other.ss1;
ss2+=other.ss2;
s1+=other.s1;
s2+=other.s2;
}
};
struct el{
int old,cur,i,j;
double dist;
el(int old = 0, int cur = 0, int i =0, int j = 0, double dist = 0) :
old(old), cur(cur), i(i), j(j), dist(dist) {}
bool operator< (const el& l) const {
return tie(dist,old,cur,i,j)<tie(l.dist,l.old,l.cur,l.i,l.j);
}
};
vector<star> V;
struct UF {
vi e;
UF(int n) : e(n, -1) {}
bool sameSet(int a, int b) { return find(a) == find(b); }
int size(int x) { return -e[find(x)]; }
int find(int x) { return e[x] < 0 ? x : e[x] = find(e[x]); }
bool join(int a, int b) {
a = find(a), b = find(b);
if (a == b) return false;
if (e[a] > e[b]) swap(a, b);
e[a] += e[b]; e[b] = a;
V[a].merge(V[b]);
return true;
}
};
int main()
{
int n;
cin>>n;
vi time(n,0);
FOR(i,n) time[i] = 0;
FOR(i,n){
P p; cin>>p.x>>p.y;
V.pb(star(p));
}
set<el> pq;
FOR(i,n){
FOR(j,i){
assert(V[j].dist(V[i])==V[i].dist(V[j]));
pq.insert(el(0,0,j,i,V[j].dist(V[i])));
}
}
UF dj(n);
FOR(i,n-1){
el ff = *pq.begin();
pq.erase(pq.begin());
set<int> unique;
FOR(j,n){
if(dj.find(j)==dj.find(ff.i) || dj.find(j)==dj.find(ff.j)) continue;
unique.insert(dj.find(j));
}
for(int x: unique){
int u = min(x,dj.find(ff.i));
int v = max(x,dj.find(ff.i));
int t1 = min(time[u],time[v]);
int t2 = max(time[u],time[v]);
pq.erase(pq.find(el(t1,t2,u,v,V[u].dist(V[v]))));
u = min(x,dj.find(ff.j));
v = max(x,dj.find(ff.j));
t1 = min(time[u],time[v]);
t2 = max(time[u],time[v]);
pq.erase(pq.find(el(t1,t2,u,v,V[u].dist(V[v]))));
}
assert(dj.join(ff.i,ff.j));
time[dj.find(ff.i)] = i+1;
cout<<dj.size(ff.i)<<endl;
for(int x: unique){
int u = min(x,dj.find(ff.i));
int v = max(x,dj.find(ff.i));
int t1 = min(time[u],time[v]);
int t2 = max(time[u],time[v]);
pq.insert(el(t1,t2,u,v,V[u].dist(V[v])));
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 3592kb
input:
2 0 0 1 0
output:
2
result:
ok single line: '2'
Test #2:
score: -100
Wrong Answer
time: 3547ms
memory: 128780kb
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 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 10...
result:
wrong answer 2nd lines differ - expected: '2', found: '3'