Advertisement
ismaeil

F

May 25th, 2022
484
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct Event
  6. {
  7.     int x ,y1 ,y2 ,type;
  8.     Event(): x(0) ,y1(0) ,y2(0) ,type(0) {}
  9.     Event(int _x ,int _y1 ,int _y2 ,int _type): x(_x) ,y1(_y1) ,y2(_y2) ,type(_type) {}
  10. };
  11.  
  12. struct Rectangle
  13. {
  14.     int x1 ,y1 ,x2 ,y2;
  15.     Rectangle(): x1(0) ,y1(0) ,x2(0) ,y2(0) {}
  16.     Rectangle(int _x1 ,int _y1 ,int _x2 ,int _y2): x1(_x1) ,y1(_y1) ,x2(_x2) ,y2(_y2) {}
  17. };
  18.  
  19. class SegTree
  20. {
  21.     private:
  22.         #define lf (p << 1)
  23.         #define rg (lf | 1)
  24.  
  25.         vector< long long > lazy;
  26.         vector< long long > st;
  27.         int n;
  28.  
  29.         long long conquer(long long stL ,long long stR)
  30.         {
  31.             return stL + stR;
  32.         }
  33.  
  34.         void UPD(int i ,int j ,long long v ,int p ,int L ,int R)
  35.         {
  36.             if( R < i || j < L ) return;
  37.  
  38.             if( i <= L && R <= j )
  39.             {
  40.                 lazy[p] += v;
  41.                 if( lazy[p] > 0 ){
  42.                     st[p] = R - L + 1;
  43.                 } else if( L == R ){
  44.                     st[p] = 0;
  45.                 } else {
  46.                     st[p] = conquer(st[lf] ,st[rg]);
  47.                 }
  48.                 return;
  49.             }
  50.  
  51.             int M = (L + R) >> 1;
  52.             UPD(i ,j ,v ,lf ,L ,M);
  53.             UPD(i ,j ,v ,rg ,M + 1 ,R);
  54.  
  55.             if( lazy[p] == 0 ){
  56.                 st[p] = conquer(st[lf] ,st[rg]);
  57.             }
  58.         }
  59.  
  60.     public:
  61.         SegTree(int sz)
  62.         {
  63.             n = sz;
  64.             st.assign(4 * n ,0);
  65.             lazy.assign(4 * n ,0);
  66.         }
  67.  
  68.         void UPD(int L ,int R ,long long v)
  69.         {
  70.             UPD(L ,R ,v ,1 ,0 ,n - 1);
  71.         }
  72.  
  73.         long long QRY()
  74.         {
  75.             return st[1];
  76.         }
  77. };
  78.  
  79. long long areaOfRectangleUnion(int &n ,vector< Rectangle > &rects)
  80. {
  81.     // the y2 in rect[i] should be decreased by 1 to calculate [y1 y2] inclusive on the yAxis.
  82.  
  83.     int stSize = 0;
  84.     vector< Event > E;
  85.     for(int i = 0 ; i < n ; i++)
  86.     {
  87.         E.emplace_back(rects[i].x1 ,rects[i].y1 ,max(rects[i].y1 ,rects[i].y2 - 1) ,+1);
  88.         E.emplace_back(rects[i].x2 ,rects[i].y1 ,max(rects[i].y1 ,rects[i].y2 - 1) ,-1);
  89.         stSize = max(stSize ,rects[i].y2);
  90.     }
  91.  
  92.     sort(E.begin(), E.end() ,[&](Event e1 ,Event e2){
  93.         if( e1.x < e2.x ) return true;
  94.         if( e1.x > e2.x ) return false;
  95.         return e1.type > e2.type;
  96.     });
  97.  
  98.     SegTree st(stSize);
  99.     long long area = 0 ,last = INT_MIN;
  100.  
  101.     for(Event e : E)
  102.     {
  103.         area += st.QRY() * (long long)(e.x - last);
  104.         st.UPD(e.y1 ,e.y2 ,e.type);
  105.         last = e.x;
  106.     }
  107.  
  108.     return area;
  109. }
  110.  
  111. Rectangle lineToRect(Rectangle line ,int r ,Rectangle border)
  112. {
  113.     return Rectangle (
  114.         max(line.x1 - r ,border.x1),
  115.         max(line.y1 - r ,border.y1),
  116.         min(line.x2 + r ,border.x2),
  117.         min(line.y2 + r ,border.y2)
  118.     );
  119. }
  120.  
  121. bool f(int r ,long long lowerBoundArea ,int n ,vector< Rectangle > &lines ,Rectangle border)
  122. {
  123.     vector< Rectangle > rects;
  124.     for(Rectangle line : lines){
  125.         rects.emplace_back(lineToRect(line ,r ,border));
  126.     }
  127.  
  128.     return lowerBoundArea <= areaOfRectangleUnion(n ,rects);
  129. }
  130.  
  131. int main()
  132. {
  133.     int n;
  134.     scanf("%d" ,&n);
  135.  
  136.     vector< Rectangle > lines;
  137.     for(int i = 0 ; i < n ; i++)
  138.     {
  139.         int x1 ,y1; scanf("%d%d" ,&x1 ,&y1);
  140.         int x2 ,y2; scanf("%d%d" ,&x2 ,&y2);
  141.  
  142.         if( x1 > x2 ) swap(x1 ,x2);
  143.         if( y1 > y2 ) swap(y1 ,y2);
  144.  
  145.         lines.emplace_back(x1 ,y1 ,x2 ,y2);
  146.     }
  147.  
  148.     int p;
  149.     scanf("%d" ,&p);
  150.  
  151.     Rectangle border;
  152.     scanf("%d%d" ,&border.x1 ,&border.y1);
  153.     scanf("%d%d" ,&border.x2 ,&border.y2);
  154.  
  155.     long long totalArea = (border.x2 - border.x1) * 1ll * (border.y2 - border.y1);
  156.     long long lowerBoundArea = (99ll + totalArea * p) / 100ll;
  157.  
  158.     int L = 1 ,R = 100100;
  159.     for(int i = 0 ; i < 30 ; i++)
  160.     {
  161.         int M = (L + R) >> 1;
  162.         f(M ,lowerBoundArea ,n ,lines ,border) ? R = M : L = M;
  163.     }
  164.  
  165.     printf("%d\n" ,R);
  166.     return 0;
  167. }
Advertisement
RAW Paste Data Copied
Advertisement