鬼畜随机化
正解是每次把三个向量选两个出来合并，三个向量的最大值是 $r$，那么必定能合出一个 $\leq r$ 的向量。这个画一个圆就好了。
但是这样很难写。考虑贪心。每次走“使得走完所到的点距离最近”的向量。显然是不对的。那我们随机化就好了（误）
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
| #include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <ctime>
#include <cmath>
using namespace std;
int n, c[100005];
struct Point{
double x, y;
int id;
}pt[100005];
int main(){
cin>>n;
for(int i=1; i<=n; i++){
scanf("%lf %lf", &pt[i].x, &pt[i].y);
pt[i].id = i;
}
while(true){
srand(time(NULL));
random_shuffle(pt+1, pt+1+n);
double x=pt[1].x, y=pt[1].y;
c[pt[1].id] = 1;
for(int i=2; i<=n; i++){
double xa=x+pt[i].x, ya=y+pt[i].y;
double xb=x-pt[i].x, yb=y-pt[i].y;
if(xa*xa+ya*ya>=xb*xb+yb*yb){
x = xb; y = yb;
c[pt[i].id] = -1;
}
else{
x = xa; y = ya;
c[pt[i].id] = 1;
}
}
if(sqrt(x*x+y*y)<=1.5*(1e6)){
for(int i=1; i<=n; i++) printf("%d ", c[i]);
printf("\n");
return 0;
}
}
return 0;
}
|