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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long double ldouble;
const int N = 1005;
const ldouble EPS = 1e-12;
#define con(typ) const typ &
#define sec second
#define fir first
template<class typ> typ iAbs(con(typ) key) {return key < 0 ? -key : key;}
template<class typ> int sgn(con(typ) key) {
if ( iAbs(key) <= EPS ) return 0;
return key < 0 ? -1 : 1;
}
struct Vector {
ldouble x, y;
Vector() {}
Vector(con(ldouble) _x, con(ldouble) _y) : x(_x), y(_y) {}
ldouble len() const {return x * x + y * y;}
Vector operator - (con(Vector) p) const {
return Vector(x - p.x, y - p.y);
}
Vector operator + (con(Vector) p) const {
return Vector(x + p.x, y + p.y);
}
friend ldouble dot(con(Vector) p, con(Vector) q) {
return p.x * q.x + p.y * q.y;
}
Vector operator -() const {return Vector(-x, -y);}
bool operator != (con(Vector) p) const {
return sgn(x - p.x) || sgn(y - p.y);
}
bool operator < (con(Vector) p) const {
if ( sgn(x - p.x) ) return sgn(x - p.x) < 0;
return sgn(y - p.y) < 0;
}
Vector cwise90() const {return Vector(y, -x);}
} sum[N];
struct Data {
Vector v; int cnt;
Data() {}
Data(con(Vector) _v, con(int) _c) : v(_v), cnt(_c) {}
} dat[N];
int nn, n, ndv;
pair<int, int> inp[N];
int cnt[N], rnk[N];
ldouble ans[N];
struct Divi {
int a, b;
ldouble ang;
Divi() {}
Divi(con(int) _a, con(int) _b, con(ldouble) _ang)
: a(_a), b(_b), ang(_ang) {}
bool operator == (con(Divi) p) const {return !sgn(ang - p.ang);}
static bool cmpAng(con(Divi) p, con(Divi) q) {return sgn(p.ang - q.ang) < 0;}
static bool cmpID(con(Divi) p, con(Divi) q) {
if ( rnk[p.a] != rnk[q.a] ) return rnk[p.a] < rnk[q.a];
return rnk[p.b] < rnk[q.b];
}
} dv[N * N];
void init() {
sum[0] = Vector(0, 0);
for (int i = 1, tmp = 0; i <= n; i++) {
for (int j = 1; j <= dat[i].cnt; j++) {
tmp++;
sum[tmp] = sum[tmp - 1] + dat[i].v;
ans[tmp] = sum[tmp].len();
}
rnk[i] = i, cnt[i] = tmp;
}
}
void done(con(int) p, con(int) q) {
int tmp = cnt[rnk[p] - 1];
for (int i = 1; i <= dat[q].cnt; i++) {
tmp++;
sum[tmp] = sum[tmp - 1] + dat[q].v;
ans[tmp] = max(ans[tmp], sum[tmp].len());
}
cnt[rnk[p]] = tmp;
for (int i = 1; i <= dat[p].cnt; i++) {
tmp++;
sum[tmp] = sum[tmp - 1] + dat[p].v;
ans[tmp] = max(ans[tmp], sum[tmp].len());
}
swap(rnk[p], rnk[q]);
}
int main() {
scanf("%d", &nn);
for (int i = 1; i <= nn; i++)
scanf("%d%d", &inp[i].fir, &inp[i].sec);
sort(inp + 1, inp + 1 + nn);
for (int i = 1; i <= nn;) {
int j = i;
while ( j <= nn && inp[i] == inp[j] ) j++;
dat[++n] = Data(Vector(inp[i].fir, inp[i].sec), j - i);
inp[n] = inp[i];
i = j;
}
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++) {
double k1 = atan2(inp[j].fir - inp[i].fir, inp[i].sec - inp[j].sec),
k2 = atan2(inp[i].fir - inp[j].fir, inp[j].sec - inp[i].sec);
dv[++ndv] = Divi(j, i, k1);
dv[++ndv] = Divi(i, j, k2);
}
sort(dv + 1, dv + 1 + ndv, Divi::cmpAng);
init();
for (int i = 1; i <= ndv; ) {
int j = i;
while ( j <= ndv && dv[i] == dv[j] ) j++;
sort(dv + i, dv + j, Divi::cmpID);
while ( i < j ) {
done(dv[i].a, dv[i].b);
i++;
}
}
for (int i = 1; i <= nn; i++)
printf("%.8f\n", (double)sqrt(ans[i]));
return 0;
}
|
