Guest User

Untitled

a guest
Apr 10th, 2012
353
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.73 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstdio>
  4. #include <cmath>
  5. using namespace std;
  6. #define forn(i, n) for (int i = 0; i < (int)(n); i++)
  7. const int maxn = 55;
  8. typedef double ld;
  9. const ld inf = 1e40;
  10. const ld eps = 1e-9;
  11. #define eq(x, y) (abs((x)-(y))<eps)
  12. #define lt(x, y) ((x)<(y)-eps)
  13. #define le(x, y) ((x)<=(y)+eps)
  14. #define sqr(x) ((x)*(x))
  15. #define op operator
  16.  
  17. struct pt
  18. {
  19.     ld x, y;
  20.     pt(){}
  21.     pt(ld X, ld Y): x(X), y(Y) {}
  22.    
  23.     pt op+ (const pt& p) {return pt(x+p.x, y+p.y);}
  24.     pt op- (const pt& p) {return pt(x-p.x, y-p.y);}
  25.     ld op* (const pt& p) {return x*p.y - y*p.x;}
  26.     pt op* (const ld& k) {return pt(x*k, y*k);}
  27.     ld dist(const pt& p) {return sqrt(sqr(x-p.x) + sqr(y-p.y));}
  28. };
  29.  
  30. ld sq(pt a, pt b, pt c)
  31. {
  32.     return 0.5 * ((b-a) * (c-a));
  33. }
  34.  
  35. int n;
  36. pt p[maxn];
  37. ld needsq;
  38.  
  39. int nxt(int i) {return (i == n-1) ? 0 : (i + 1);}
  40. int prv(int i) {return (i == 0) ? n-1 : (i - 1);}
  41.  
  42. ld f(int i, ld k)
  43. {
  44.     ld lft = needsq;
  45.     pt t = p[i] * (1-k) + p[nxt(i)] * k;
  46.     int j = nxt(i);
  47.     while (sq(t, p[j], p[nxt(j)]) < lft)
  48.     {
  49.         lft -= sq(t, p[j], p[nxt(j)]);
  50.         j = nxt(j);
  51.     }
  52.    
  53.     ld cf = lft / sq(t, p[j], p[nxt(j)]);
  54.     pt opp = p[j] * (1-cf) + p[nxt(j)] * cf;
  55.     return t.dist(opp);
  56. }
  57.  
  58. ld solve()
  59. {
  60.     needsq = 0;
  61.     forn(i, n-2)
  62.         needsq += sq(p[0], p[i+1], p[i+2]);
  63.     needsq /= 2;
  64.    
  65.     ld mn = inf;
  66.     forn(i, n)
  67.     {
  68.         ld l = 0, r = 1, m1, m2, v1, v2;
  69.         forn(III, 100)
  70.         {
  71.             m1 = (l + l + r) / 3.;
  72.             m2 = (l + r + r) / 3;
  73.             v1 = f(i, m1);
  74.             v2 = f(i, m2);
  75.             if (v1 > v2)
  76.                 l = m1;
  77.             else
  78.                 r = m2;
  79.         }
  80.         mn = min(mn, f(i, l));
  81.     }
  82.     return mn;
  83. }
  84.  
  85. int main()
  86. {
  87.     cin >> n;
  88.     forn(i, n) cin >> p[i].x >> p[i].y;
  89.    
  90.     cout.precision(10);
  91.     cout << fixed << solve() << endl;
  92.    
  93.     return 0;
  94. }
Advertisement
Add Comment
Please, Sign In to add comment