fork download
copy 
  1. int32_t main() {
  2.  
  3.   ios_base::sync_with_stdio(0);
  4.   cout << fixed << setprecision(10);
  5.   cerr << fixed << setprecision(10);
  6.   cin.tie(0);
  7.   //double beg_clock = 1.0 * clock() / CLOCKS_PER_SEC;
  8.  
  9.   int n, L;
  10.   cin>>n>>L;
  11.   vector<Point> pt;
  12.   RE (i, n) {
  13.     int x, y;
  14.     cin>>x>>y;
  15.     pt.PB({(LD)x, (LD)y});
  16.   }
  17.   reverse(ALL(pt));
  18.   REP (tr, 2) {
  19.     REP (i, n) {
  20.       pt.PB(pt[i]);
  21.     }
  22.   }
  23.   vector<LD> pref(3 * n);
  24.   RE (i, 3 * n - 2) {
  25.     pref[i] = pref[i - 1] + pt[i - 1].Dist(pt[i]);
  26.   }
  27.   Point orig{(LD)0, (LD)0};
  28.   LD area = 0;
  29.   int fin = -1;
  30.   RE (i, n) {
  31.     function<bool(int)> Check = [&](int j) {
  32.       if (j > i + n - 1) { return false; }
  33.       LD used = pref[j] - pref[i];
  34.       LD rem = L - used;
  35.       LD long_ax = rem / 2;
  36.       assert(rem > pt[i].Dist(pt[j]) + kEps);
  37.       LD short_ax = sqrt(Sq(rem / 2) - Sq(pt[i].Dist(pt[j]) / 2));
  38.       LD rat = long_ax / short_ax;
  39.       Point M = (pt[i] + pt[j]) / 2;
  40.       Point OX = (pt[i] - M).Normalize();
  41.       Point OY = OX.Rotate(kPi / 2);
  42.       function<Point(Point)> Transform = [&](Point P) {
  43.         P = P - M;
  44.         return Point{OX.DotProd(P) / rat, OY.DotProd(P)};
  45.       };
  46.       function<Point(Point)> Back = [&](Point P) {
  47.         return M + OX * P.x * rat + OY * P.y;
  48.       };
  49.       Circle O = {orig, short_ax};
  50.       Line fi = {Transform(pt[i - 1]), Transform(pt[i])};
  51.       Line si = {Transform(pt[i]), Transform(pt[i + 1])};
  52.       Line fj = {Transform(pt[j - 1]), Transform(pt[j])};
  53.       Line sj = {Transform(pt[j]), Transform(pt[j + 1])};
  54.       function<LD(Line, LD)> GetX = [&](Line k, LD def) {
  55.         vector<Point> inters = Utils::InterCircleLine(O, k);
  56.         assert(SZ(inters) == 2);
  57.         //assert((inters[0].y > 0) + (inters[1].y > 0) == 1);
  58.         if (inters[0].y > kEps) { return inters[0].x; }
  59.         if (inters[1].y > kEps) { return inters[1].x; }
  60.         return def;
  61.       };
  62.       LD from = max(GetX(fi, -short_ax), GetX(fj, -short_ax));
  63.       LD to = min(GetX(si, short_ax), GetX(sj, short_ax));
  64.       debug(i, j, from, to);
  65.       if (from > to) { return false; }
  66.       LD alfa2 = acos(from / short_ax);
  67.       LD alfa1 = acos(to / short_ax);
  68.       LD alfa = alfa2 - alfa1;
  69.       assert(alfa >= -kEps);
  70.       LD odcinek = ((alfa - sin(alfa)) / 2) * Sq(short_ax);
  71.       Point B1 = Back({from, sqrt(Sq(short_ax) - Sq(from))});
  72.       Point B2 = Back({to, sqrt(Sq(short_ax) - Sq(to))});
  73.       debug(B1, B2);
  74.       area += odcinek * rat;
  75.       area += (B2.x - B1.x) * (B1.y + B2.y) / 2;
  76.       return true;
  77.     };
  78.     maxi(fin, i + 1);
  79.     int cnt_fails = 0;
  80.     int cnt_succs = 0;
  81.     while (1) {
  82.       if (Check(fin)) {
  83.         cnt_fails = 0;
  84.         cnt_succs++;
  85.       } else {
  86.         if (cnt_succs) {
  87.           fin--;
  88.           break;
  89.         }
  90.         cnt_fails++;
  91.       }
  92.       fin++;
  93.       if (cnt_fails == 3) {
  94.         fin -= 3;
  95.       }
  96.     }
  97.   }
  98.   cout<<area<<endl;
  99.  
  100.  
  101.   return 0;
  102. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:1:1: error: ‘int32_t’ does not name a type; did you mean ‘char32_t’?
 int32_t main() {
 ^~~~~~~
 char32_t
stdout
copy 
Standard output is empty
https://ideone.com/OovtSS
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!