Submission #232811

#TimeUsernameProblemLanguageResultExecution timeMemory
232811pedy4000Svjetlost (COI18_svjetlost)C++14
14 / 100
121 ms17400 KiB
#include <algorithm> #include <iostream> #include <iomanip> #include <vector> #include <cmath> #include <set> using namespace std; typedef long long ll; typedef long double ld; typedef pair <ll, ll> point; #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 (stderr)

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...