Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define _ ios_base::sync_with_stdio(0);cin.tie(0);
- //#define endl '\n'
- #define f first
- #define s second
- #define pb push_back
- typedef long long ll;
- const int INF = 0x3f3f3f3f;
- const ll LINF = 0x3f3f3f3f3f3f3f3fll;
- typedef double ld;
- const ld eps = 1e-9;
- #define sq(x) ((x)*(x))
- bool eq(ld a, ld b) {
- return abs(a-b) <= eps;
- }
- struct pt {
- ld x, y;
- pt() {}
- pt(ld x2, ld y2) : x(x2), y(y2) {}
- bool operator < (const pt p) const {
- if (!eq(x, p.x)) return x < p.x;
- return y < p.y;
- }
- bool operator == (const pt p) const {
- return eq(x, p.x) and eq(y, p.y);
- }
- pt operator + (const pt p) const { return pt(x+p.x, y+p.y); }
- pt operator - (const pt p) const { return pt(x-p.x, y-p.y); }
- pt operator * (const ld c) const { return pt(x * c, y * c); }
- pt operator / (const ld c) const { return pt(x / c, y / c); }
- };
- struct line {
- pt p, q;
- line() {}
- line(pt p2, pt q2) : p(p2), q(q2) {}
- };
- ld dist(pt p, pt q) {
- //return sqrt(dist2(p, q));
- return hypot(p.x-q.x, p.y-q.y);
- }
- ld dot(pt u, pt v) {
- return u.x*v.x + u.y*v.y;
- }
- ld norm(pt v) {
- return dist(pt(0, 0), v);
- }
- bool mesmo(pt v, pt w) {
- return dot(v, w) > 0;
- }
- ld cross(pt u, pt v) {
- return u.x*v.y - u.y*v.x;
- }
- ld sarea(pt p, pt q, pt r) {
- return cross(q-p, r-q)/2;
- }
- bool ccw(pt p, pt q, pt r) {
- return sarea(p, q, r) > 0;
- }
- pt proj(pt p, line r) {
- if (r.p == r.q) return r.p;
- r.q = r.q - r.p; p = p - r.p;
- pt proj = r.q*(dot(p, r.q)/dot(r.q, r.q));
- return proj+r.p;
- }
- ld disttoline(pt p, line r) {
- return dist(p, proj(p, r));
- }
- vector<pt> convexhull(vector<pt> v) {
- vector<pt> l, u;
- sort(v.begin(), v.end());
- for (int i = 0; i < v.size(); i++) {
- while (l.size() > 1 and !ccw(v[i], l.back(), l[l.size()-2])) l.pop_back();
- l.pb(v[i]);
- }
- for (int i = v.size()-1; i+1; i--) {
- while (u.size() > 1 and !ccw(v[i], u.back(), u[u.size()-2])) u.pop_back();
- u.pb(v[i]);
- }
- l.pop_back(), u.pop_back();
- for (auto i : u) l.pb(i);
- return l;
- }
- int main() { _
- int n; cin >> n;
- vector<pt> v;
- for (int i = 0; i < n; i++) {
- int a, b; cin >> a >> b;
- v.pb(pt(a, b));
- }
- v = convexhull(v);
- reverse(v.begin(), v.end());
- int p1=1, p2=1, p3=1;
- ld ans = 1e16;
- vector<pt> anss;
- for (int ii = 0; ii < v.size(); ii++) {
- pt i = v[ii], j = v[(ii+1)%v.size()];
- line l = line(i, j);
- while (1) {
- pt pro = proj(v[p1], l), pro1 = proj(v[(p1+1)%v.size()], l);
- if (!mesmo(pro1-pro, j-i)) break;
- p1 = (p1+1)%v.size();
- }
- while (1) {
- if (disttoline(v[(p2+1)%v.size()], l) < disttoline(v[p2], l)) break;
- p2 = (p2+1)%v.size();
- }
- p3 = p2;
- while (p3 != ii) {
- pt pro = proj(v[p3], l), pro1 = proj(v[(p3+1)%v.size()], l);
- if (!mesmo(pro1-pro, i-j)) break;
- p3 = (p3+1)%v.size();
- }
- pt soma = v[p2] - proj(v[p2], l);
- pt ini = proj(v[p3], l), fim = proj(v[p1], l);
- vector<pt> at = {ini, fim, fim+soma, ini+soma};
- ld atval = norm(soma)*norm(fim-ini);
- if (atval < ans) {
- ans = atval;
- anss = at;
- }
- if (p1 == ii) p1++;
- }
- cout << fixed << setprecision(12);
- for (auto i : anss) cout << i.x << " " << i.y << endl;
- exit(0);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement