Problem: Codeforces 995C Leaving the Bar
Given n two-dimensional vectors $\vec v_{i}$ and n intergers $ c_{1},c_{2},…c_{n} $. It’s guaranteed that $ |v| \le 1e6 $ and $ c_{i} = 1 or -1 $. Let $\vec p = \sum_{i=1}^{n} c_{i}\vec v_{i}$. Determine the value of $c_{i}$ to satisfy $|p| \le 1.5 \cdot 1e6$.
As n is at most $10^{5}$, it is impossible to enumerate all the cases.
The key to solve this problem is such a conclusion:
Given 3 vectors $\vec v$, $|v| \le R$, we can always get some $\vec v_{i} + \vec v_{j}$ or $\vec v_{i} - \vec v_{j}$ that has length at least R.
With the opposite vectors of the 3 vectors, there are 6 vectors altogether now. So if we divide the plane into 6 60-degree sectors, there is at least one sector that contains two vectors(they are not the opposite for sure). Pretty good.
So we can merge vectors until there are only 2 vectors.
We always pick 3 vectors and merge 2 of them if the length of the result vector is less equal than 1e6.
And we can ensure that length of the sum or difference of the last 2 vectors is less equal than $\sqrt{2} \cdot 1e6 \le 1.5 \cdot 1e6$.
My Code:1
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
103
104
105
106
107
108
109
110
using namespace std;
const int N=100010;
const int R=1000000;
const db eps=1e-8;
struct P {
db x,y;
P(){}
P(db xx,db yy):x(xx),y(yy){}
P operator+(P rhs) {
return P(x+rhs.x,y+rhs.y);
}
P operator-(P rhs) {
return P(x-rhs.x,y-rhs.y);
}
P operator*(db k) {
return P(k*x,k*y);
}
db dot(P rhs) {
return x*rhs.x+y*rhs.y;
}
db det(P rhs) {
return x*rhs.y-y*rhs.x;
}
};
struct node {
int ls,rs,type;
};
int n,tot=0;
P vec[2*N];
node nd[2*N];
int ans[N];
void dfs(int id,int type) {
if (nd[id].ls==-1) {
ans[id]=type;
return;
}
dfs(nd[id].ls,type);
dfs(nd[id].rs,type*nd[id].type);
}
int main()
{
scanf("%d",&n);
queue<int> q;
for (int i=0;i<n;i++) {
scanf("%lf%lf",&vec[tot].x,&vec[tot].y);
nd[tot++]={-1,-1,1};
q.push(i);
}
while (q.size()>2) {
int a[3]={-1};
for (int i=0;i<3;i++) {
a[i]=q.front();
q.pop();
}
int x=-1,y=-1,type=1;
for (int i=0;i<3&&x==-1;i++) {
for (int j=i+1;j<3&&x==-1;j++) {
if (sqrt((vec[a[i]]+vec[a[j]]).dot(vec[a[i]]+vec[a[j]]))<R+eps) {
x=a[i],y=a[j];
break;
}
if (sqrt((vec[a[i]]-vec[a[j]]).dot(vec[a[i]]-vec[a[j]]))<R+eps) {
x=a[i],y=a[j],type=-1;
break;
}
}
}
for (int i=0;i<3;i++) {
if (a[i]!=x&&a[i]!=y) q.push(a[i]);
}
nd[tot]={x,y,type};
vec[tot]=vec[x]+(vec[y]*type);
q.push(tot++);
}
if (q.size()<2) {
printf("1\n");
return 0;
}
int x=q.front();q.pop();
int y=q.front();q.pop();
if (sqrt((vec[x]+vec[y]).dot(vec[x]+vec[y]))<sqrt(2)*R+eps) {
nd[tot++]={x,y,1};
} else {
nd[tot++]={x,y,-1};
}
dfs(tot-1,1);
for (int i=0;i<n;i++) printf("%d ",ans[i]);
printf("\n");
}