Codeforces Round #492 (Div. 1) C - Leaving the Ba

2019-04-14 08:28发布

站内文章 / 模拟电子
13588 0 1663
题意: 给出n个向量，令一些向量反向使得所有向量的和的长度不超过1.5e6，其中每个向量长度不超过1e6，n <= 1e5 分析: 任选三个向量，他们本身和他们的反向中总能选出两个相互夹角大于120°的向量，这样就可以让向量长度减少，每次选出三个做即可，实现时用一个集合表示某些向量的和，并用带权并查集维护是否反向 #include #define pii pair #define fi first #define se second #define mk make_pair #define sc(x) scanf("%d", &x) #define pb push_back #define debug puts("???") #define ABS(x) ((x)<0?(-x):(x)); typedef long long LL; using namespace std; const int mod = 998244353; const int maxn = 1e5+10; struct Vector{ int x, y; Vector(int x=0, int y=0):x(x),y(y){} } a[maxn], ans; Vector operator + (Vector a, Vector b){return Vector(a.x+b.x,a.y+b.y);} Vector operator - (Vector a, Vector b){return Vector(a.x-b.x,a.y-b.y);} Vector operator * (int p, Vector a){return Vector(a.x*p, a.y*p);} LL Len(Vector a){ return 1LL*a.x*a.x+1LL*a.y*a.y;} set st; int n, f[maxn], g[maxn], v[3]; int Find(int x){ if(f[x] == x) return f[x]; int fx = Find(f[x]); g[x] *= g[f[x]]; return f[x] = fx; } void join(int x, int y, int k){ int fx = Find(x), fy = Find(y); g[fy] = k; f[fy] = fx; } void print(Vector v){ printf("(%d,%d)",v.x,v.y); } void solve(){ set::iterator it = st.begin(); for(int i = 0; i < 3; i++){ v[i] = *it; it++; for(int j = 0; j < i; j++){ Vector v1 = a[v[i]], v2 = a[v[j]]; //print(v1); print(v2); print(v1+v2); print(v1-v2); puts(""); if(Len(v1+v2) <= max(Len(v1), Len(v2))){ join(v[i], v[j], 1); a[v[i]] = a[v[i]] + a[v[j]]; st.erase(v[j]); return; } if(Len(v1-v2) <= max(Len(v1), Len(v2))){ join(v[i], v[j], -1); a[v[i]] = a[v[i]] - a[v[j]]; st.erase(v[j]); return; } } } } void output(){ for(int i = 0; i < n; i++){ Find(i); printf("%d%c", g[i], " "[i==n-1]); } } int main(){ sc(n); for(int i = 0; i < n; i++){ sc(a[i].x); sc(a[i].y); f[i] = i; g[i] = 1; st.insert(i); } while(st.size() > 2){ //printf("%d ", st.size()); solve(); } if(st.size() == 1) output(); else{ set::iterator it = st.begin(); int x = *it; it++; int y = *it; Vector v1 = a[x], v2 = a[y]; if(Len(v1+v2) > Len(v1-v2)){ join(x, y, -1); }else{ join(x, y, 1); } output(); } return 0; }  

热门文章