#include <algorithm>
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <set>
using namespace std;
typedef pair <int, int> point;
typedef long double ld;
typedef long long ll;
#define X first
#define Y second
point operator- (point a, point b) {
return point(a.X - b.X, a.Y - b.Y);
}
ll operator* (point a, point b) {
return a.X * b.Y - a.Y * b.X;
}
bool intersect (point a, point b, point c, point d) {
point v = b - a, u = c - d;
if (u * v == 0)
return false;
if (0 < (u * v))
return (u * v) <= ((a - d) * v);
return (u * v) >= ((a - d) * v);
}
ld distance (point a, point b) {
return sqrt((a.X - b.X) * (a.X - b.X) + (a.Y - b.Y) * (a.Y - b.Y));
}
const int N = 1e5 + 5;
int n;
point p[N];
ld res[N << 2];
ld lazy[N << 2];
int lst[N << 2];
ld len[N << 2];
set <int> live;
int dist (int a, int b) {
return a < b? b - a: n - a + b;
}
int nxt (int a) {
return (a + 1) % n;
}
ld getLen (int l, int r, int s = 0, int e = n, int id = 1) {
if (l <= s && e <= r)
return len[id];
if (r <= s || e <= l)
return 0;
int mid = e + s >> 1;
return getLen(l, r, s, mid, id << 1) + getLen(l, r, mid, e, id << 1 | 1);
}
ld calcLen (int l, int r) {
if (l <= r)
return getLen(l, r + 1);
return getLen(l, n) + getLen(0, r + 1);
}
int calc (int d) {
int s = nxt(d), e = d;
while (dist(s, e) > 1) {
int mid = (s + dist(s, e) / 2) % n;
if (intersect(p[d], p[nxt(d)], p[mid], p[nxt(mid)]))
s = mid;
else
e = mid;
}
return s;
}
void buildLen (int s = 0, int e = n, int id = 1) {
if (e - s == 1) {
len[id] = distance(p[s], p[nxt(s)]);
return ;
}
int mid = e + s >> 1;
buildLen(s, mid, id << 1);
buildLen(mid, e, id << 1 | 1);
len[id] = len[id << 1] + len[id << 1 | 1];
}
void buildResLst (int s = 0, int e = n, int id = 1) {
if (e - s == 1) {
lst[id] = calc(s);
res[id] = calcLen(s, lst[id]);
return ;
}
int mid = e + s >> 1;
buildResLst(s, mid, id << 1);
buildResLst(mid, e, id << 1 | 1);
res[id] = max(res[id << 1], res[id << 1 | 1]);
}
void preProcess() {
for (int i = 0; i < n; i++)
live.insert(i);
for (int i = 0; i < (N << 2); i++)
lst[i] = -1;
buildLen();
buildResLst();
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> n;
for (int i = 0; i < n; i++)
cin >> p[i].X >> p[i].Y;
preProcess();
cout << fixed << setprecision(6) << res[1] << "\n";
return 0;
}
Compilation message
svjetlost.cpp: In function 'ld getLen(int, int, int, int, int)':
svjetlost.cpp:62:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = e + s >> 1;
~~^~~
svjetlost.cpp: In function 'void buildLen(int, int, int)':
svjetlost.cpp:90:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = e + s >> 1;
~~^~~
svjetlost.cpp: In function 'void buildResLst(int, int, int)':
svjetlost.cpp:103:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = e + s >> 1;
~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
1920 KB |
Unexpected end of file - double expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
1920 KB |
Unexpected end of file - double expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1920 KB |
found '32934.3604540000', expected '32934.3604541195', error '0.0000000000' |
| 2 |
Incorrect |
7 ms |
2176 KB |
Expected double, but "-nan" found |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
2304 KB |
Expected double, but "-nan" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
1920 KB |
Unexpected end of file - double expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
