thilio

Kit polígono

Sep 24th, 2020 (edited)
1,103
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3.  
  4. using cord = long double;
  5. const long double PI = acos(-1);
  6. const long double EPS = 1e-8;
  7.  
  8. int signal(cord x) { return (x > EPS) - (x < -EPS); }
  9.  
  10. struct point {
  11.     cord x,y;
  12.  
  13.     // Constructor
  14.     point(cord _x, cord _y): x(_x), y(_y) {}
  15.     point(): x(0), y(0) {}
  16.  
  17.     // Very basic operations
  18.     void operator=  (const point& p){x = p.x; y = p.y; }
  19.     point operator+ (const point& q){ return {x + q.x, y + q.y}; }
  20.     point operator- (const point& q){ return {x - q.x, y - q.y}; }
  21.     point operator* (const cord& s) { return {x*s, y*s}; }
  22.     point operator/ (const cord& s) { return {x/s, y/s}; }
  23.  
  24.     // Basic operations
  25.     cord cross (const point &p){ return (x*p.y - y*p.x); }
  26.     cord dot (const point& p)  { return (x*p.x + y*p.y); }
  27.  
  28.     /* TRANSFORMA EM DOUBLE
  29.     point proj(const point& p) { return(p*(dot(p)/p.norm()))}
  30.     */
  31.  
  32.     // Length operations
  33.     cord norm()       { return (x*x + y*y); }
  34.     long double len() { return hypot(x, y); }
  35.  
  36.     // Rotation operations
  37.     point rotate90()              { return {-y,x}; }
  38.     // TRANSFORMA PRA DOUBLE point rotate(long double ang) { return {cos(ang)*x - sin(ang)*y, sin(ang)*x + cos(ang)*y}; }
  39.    
  40. };
  41.  
  42. #define pb push_back
  43. #define mp make_pair
  44. #define fst first
  45. #define snd second
  46.  
  47. #define fr(i,n)     for(int i=0;i<n;i++)
  48. #define frr(i,n)    for(int i=1;i<=n;i++)
  49.  
  50. #define ms(x,i) memset(x,i,sizeof(x))
  51. #define dbg(x)  cout << #x << " = " << x << endl
  52. #define all(x)  x.begin(),x.end()
  53.  
  54. #define gnl cout << endl
  55. #define olar cout << "olar" << endl
  56. #define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  57.  
  58. typedef long long int ll;
  59. typedef pair<int,int> pii;
  60. typedef vector<int> vi;
  61. typedef vector<pii> vii;
  62. typedef pair<ll,ll> pll;
  63.  
  64. const int INF = 0x3f3f3f3f;
  65. const ll llINF = 0x3f3f3f3f3f3f3f;
  66. const int MOD = 1e9+7;
  67.  
  68. long double memo[100100][2][2][2][2];
  69. point A,B;
  70.  
  71. int cc;
  72. int n;
  73. vector<point> v;
  74. /*
  75. memo[i][j][k][l][h]:
  76.     ponto i;
  77.     projetei o v_0;
  78.     projetei o v_{i-2};
  79.     projetei o v_{i-1};
  80.    
  81.     area > 0;
  82.  
  83.     bool 1 = B
  84.          0 = A
  85.  
  86. */
  87.  
  88. long double pd(int i,int pri,int pen,int ult, int posi){
  89.     point a,b;
  90.     if(pen == 0) a = v[i-2] + A;
  91.     else a = v[i-2] + B;
  92.     if(ult == 0) b = v[i-1] + A;
  93.     else b = v[i-1] + B;
  94.     a=a/2;b=b/2;
  95.  
  96.     point v0;
  97.     if(pri == 0) v0 = v[0] + A;
  98.     else v0 = v[0] + B;
  99.     v0=v0/2;
  100.  
  101.     if(i == n){
  102.  
  103.         if(signal((b-a).cross(v0 - b))*cc < 0) return (long double)llINF;
  104.  
  105.         if(posi == 1) return (long double)0;
  106.         else return (long double)llINF;
  107.     }
  108.  
  109.     long double& pdm = memo[i][pri][pen][ult][posi];
  110.     if(signal(pdm + 1) > 0) return pdm;
  111.     pdm = (long double)llINF;
  112.  
  113.    
  114.  
  115.     point tentA,tentB;
  116.     tentA = v[i] + A;
  117.     tentB = v[i] + B;
  118.     tentA = tentA/2;
  119.     tentB = tentB/2;
  120.  
  121.     if(signal((b - a).cross(tentA - b))*cc >= 0){
  122.         long double area = abs((b - v0).cross(tentA - v0));
  123.         int p;
  124.         if (posi > 0 || signal(area) > 0) p = 1;
  125.         else p = 0;
  126.         pdm = min(pdm, area + pd(i + 1,pri,ult,0,p));
  127.         dbg(pdm);
  128.     }
  129.  
  130.     if(signal((b - a).cross(tentB - b))*cc >= 0){
  131.         long double area = abs((b - v0).cross(tentB - v0));
  132.         int p;
  133.         if (posi > 0 || signal(area) > 0) p = 1;
  134.         else p = 0;
  135.         pdm = min(pdm, area + pd(i + 1,pri,ult,1,p));
  136.         dbg(pdm);
  137.     }
  138.  
  139.     //if(signal(pdm) < 0) pdm = (long double)llINF;
  140.  
  141.     return pdm;
  142.  
  143. }
  144.  
  145.  
  146. int main(){
  147.  
  148.     fastio;
  149.  
  150.     cout << setprecision(3) << fixed;
  151.    
  152.     cin >> n;
  153.  
  154.     fr(i,n){
  155.         point p;
  156.         cin >> p.x >> p.y;
  157.         v.pb(p);
  158.     }
  159.  
  160.  
  161.     fr(i,n){
  162.         if(signal((v[1] - v[0]).cross(v[i] - v[1])) != 0){
  163.             cc = signal((v[1] - v[0]).cross(v[i] - v[1]));
  164.             break;
  165.         }
  166.     }
  167.  
  168.  
  169.     cin >> A.x >> A.y >> B.x >> B.y;
  170.  
  171.     long double ans = (long double)llINF;
  172.  
  173.     ms(memo,-1);
  174.  
  175.     ans = min(ans,pd(2,0,0,0,0));
  176.     dbg(ans);
  177.     //return 0;
  178.     ans = min(ans,pd(2,1,1,0,0));
  179.     ans = min(ans,pd(2,0,0,1,0));
  180.     ans = min(ans,pd(2,1,1,1,0));
  181.  
  182.     reverse(all(v));
  183.     ms(memo,-1);
  184.  
  185.     ans = min(ans,pd(2,0,0,0,0));
  186.     ans = min(ans,pd(2,1,1,0,0));
  187.     ans = min(ans,pd(2,0,0,1,0));
  188.     ans = min(ans,pd(2,1,1,1,0));
  189.  
  190.     ans*= 4;
  191.     ans += 0.5;
  192.     ans = (ll)ans;
  193.  
  194.  
  195.     cout << ans/8 << endl;
  196.  
  197.  
  198.  
  199.  
  200. }
  201.  
RAW Paste Data