# 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