SHARE
TWEET

Untitled

a guest Jan 20th, 2020 72 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. #define _ ios_base::sync_with_stdio(0);cin.tie(0);
  6. //#define endl '\n'
  7. #define f first
  8. #define s second
  9. #define pb push_back
  10.  
  11. typedef long long ll;
  12.  
  13. const int INF = 0x3f3f3f3f;
  14. const ll LINF = 0x3f3f3f3f3f3f3f3fll;
  15.  
  16. typedef double ld;
  17.  
  18. const ld eps = 1e-9;
  19. #define sq(x) ((x)*(x))
  20.  
  21. bool eq(ld a, ld b) {
  22.     return abs(a-b) <= eps;
  23. }
  24.  
  25. struct pt {
  26.     ld x, y;
  27.     pt() {}
  28.     pt(ld x2, ld y2) : x(x2), y(y2) {}
  29.     bool operator < (const pt p) const {
  30.         if (!eq(x, p.x)) return x < p.x;
  31.         return y < p.y;
  32.     }
  33.     bool operator == (const pt p) const {
  34.         return eq(x, p.x) and eq(y, p.y);
  35.     }
  36.     pt operator + (const pt p) const { return pt(x+p.x, y+p.y); }
  37.     pt operator - (const pt p) const { return pt(x-p.x, y-p.y); }
  38.     pt operator * (const ld c) const { return pt(x * c, y * c); }
  39.     pt operator / (const ld c) const { return pt(x / c, y / c); }
  40. };
  41.  
  42. struct line {
  43.     pt p, q;
  44.     line() {}
  45.     line(pt p2, pt q2) : p(p2), q(q2) {}
  46. };
  47.  
  48. ld dist(pt p, pt q) {
  49.     //return sqrt(dist2(p, q));
  50.     return hypot(p.x-q.x, p.y-q.y);
  51. }
  52.  
  53. ld dot(pt u, pt v) {
  54.     return u.x*v.x + u.y*v.y;
  55. }
  56.  
  57. ld norm(pt v) {
  58.     return dist(pt(0, 0), v);  
  59. }
  60.  
  61. bool mesmo(pt v, pt w) {
  62.     return dot(v, w) > 0;  
  63. }
  64.  
  65. ld cross(pt u, pt v) {
  66.     return u.x*v.y - u.y*v.x;
  67. }
  68.  
  69. ld sarea(pt p, pt q, pt r) {
  70.     return cross(q-p, r-q)/2;  
  71. }
  72.  
  73. bool ccw(pt p, pt q, pt r) {
  74.     return sarea(p, q, r) > 0; 
  75. }
  76.  
  77. pt proj(pt p, line r) {
  78.     if (r.p == r.q) return r.p;
  79.     r.q = r.q - r.p; p = p - r.p;
  80.     pt proj = r.q*(dot(p, r.q)/dot(r.q, r.q));
  81.     return proj+r.p;
  82. }
  83.  
  84. ld disttoline(pt p, line r) {
  85.     return dist(p, proj(p, r));
  86. }
  87.  
  88. vector<pt> convexhull(vector<pt> v) {
  89.     vector<pt> l, u;
  90.     sort(v.begin(), v.end());
  91.     for (int i = 0; i < v.size(); i++) {
  92.         while (l.size() > 1 and !ccw(v[i], l.back(), l[l.size()-2])) l.pop_back();
  93.         l.pb(v[i]);
  94.     }
  95.     for (int i = v.size()-1; i+1; i--) {
  96.         while (u.size() > 1 and !ccw(v[i], u.back(), u[u.size()-2])) u.pop_back();
  97.         u.pb(v[i]);
  98.     }
  99.     l.pop_back(), u.pop_back();
  100.     for (auto i : u) l.pb(i);
  101.     return l;
  102. }
  103.  
  104. int main() { _
  105.     int n; cin >> n;
  106.     vector<pt> v;
  107.     for (int i = 0; i < n; i++) {
  108.         int a, b; cin >> a >> b;
  109.         v.pb(pt(a, b));
  110.     }
  111.     v = convexhull(v);
  112.     reverse(v.begin(), v.end());
  113.     int p1=1, p2=1, p3=1;
  114.  
  115.     ld ans = 1e16;
  116.     vector<pt> anss;
  117.  
  118.     for (int ii = 0; ii < v.size(); ii++) {
  119.         pt i = v[ii], j = v[(ii+1)%v.size()];
  120.         line l = line(i, j);
  121.  
  122.         while (1) {
  123.             pt pro = proj(v[p1], l), pro1 = proj(v[(p1+1)%v.size()], l);
  124.             if (!mesmo(pro1-pro, j-i)) break;
  125.             p1 = (p1+1)%v.size();
  126.         }
  127.         while (1) {
  128.             if (disttoline(v[(p2+1)%v.size()], l) < disttoline(v[p2], l)) break;
  129.             p2 = (p2+1)%v.size();
  130.         }
  131.         p3 = p2;
  132.         while (p3 != ii) {
  133.             pt pro = proj(v[p3], l), pro1 = proj(v[(p3+1)%v.size()], l);
  134.             if (!mesmo(pro1-pro, i-j)) break;
  135.             p3 = (p3+1)%v.size();
  136.         }
  137.  
  138.         pt soma = v[p2] - proj(v[p2], l);
  139.         pt ini = proj(v[p3], l), fim = proj(v[p1], l);
  140.         vector<pt> at = {ini, fim, fim+soma, ini+soma};
  141.         ld atval = norm(soma)*norm(fim-ini);
  142.         if (atval < ans) {
  143.             ans = atval;
  144.             anss = at;
  145.         }
  146.  
  147.         if (p1 == ii) p1++;
  148.     }
  149.     cout << fixed << setprecision(12);
  150.     for (auto i : anss) cout << i.x << " " << i.y << endl;
  151.     exit(0);
  152. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top