Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <cstdio>
- #include <cmath>
- using namespace std;
- #define forn(i, n) for (int i = 0; i < (int)(n); i++)
- const int maxn = 55;
- typedef double ld;
- const ld inf = 1e40;
- const ld eps = 1e-9;
- #define eq(x, y) (abs((x)-(y))<eps)
- #define lt(x, y) ((x)<(y)-eps)
- #define le(x, y) ((x)<=(y)+eps)
- #define sqr(x) ((x)*(x))
- #define op operator
- struct pt
- {
- ld x, y;
- pt(){}
- pt(ld X, ld Y): x(X), y(Y) {}
- pt op+ (const pt& p) {return pt(x+p.x, y+p.y);}
- pt op- (const pt& p) {return pt(x-p.x, y-p.y);}
- ld op* (const pt& p) {return x*p.y - y*p.x;}
- pt op* (const ld& k) {return pt(x*k, y*k);}
- ld dist(const pt& p) {return sqrt(sqr(x-p.x) + sqr(y-p.y));}
- };
- ld sq(pt a, pt b, pt c)
- {
- return 0.5 * ((b-a) * (c-a));
- }
- int n;
- pt p[maxn];
- ld needsq;
- int nxt(int i) {return (i == n-1) ? 0 : (i + 1);}
- int prv(int i) {return (i == 0) ? n-1 : (i - 1);}
- ld f(int i, ld k)
- {
- ld lft = needsq;
- pt t = p[i] * (1-k) + p[nxt(i)] * k;
- int j = nxt(i);
- while (sq(t, p[j], p[nxt(j)]) < lft)
- {
- lft -= sq(t, p[j], p[nxt(j)]);
- j = nxt(j);
- }
- ld cf = lft / sq(t, p[j], p[nxt(j)]);
- pt opp = p[j] * (1-cf) + p[nxt(j)] * cf;
- return t.dist(opp);
- }
- ld solve()
- {
- needsq = 0;
- forn(i, n-2)
- needsq += sq(p[0], p[i+1], p[i+2]);
- needsq /= 2;
- ld mn = inf;
- forn(i, n)
- {
- ld l = 0, r = 1, m1, m2, v1, v2;
- forn(III, 100)
- {
- m1 = (l + l + r) / 3.;
- m2 = (l + r + r) / 3;
- v1 = f(i, m1);
- v2 = f(i, m2);
- if (v1 > v2)
- l = m1;
- else
- r = m2;
- }
- mn = min(mn, f(i, l));
- }
- return mn;
- }
- int main()
- {
- cin >> n;
- forn(i, n) cin >> p[i].x >> p[i].y;
- cout.precision(10);
- cout << fixed << solve() << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment