Cod sursa(job #592689)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 29 mai 2011 22:15:03
Problema Oypara Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.46 kb
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

struct pct {
  double x, y;
};

const double eps = 0.00000000000000000001;

const int N = 100005;

int n, sts[N], stj[N];

pct sus[N], jos[N];

bool f[N];

void read() {
  double x, y1, y2;

  scanf("%d", &n);

  for (int i = 1; i <= n; ++ i) {
    scanf("%lf%lf%lf", &x, &y1, &y2);

    sus[i].x = x;
    sus[i].y = y2;

    jos[i].x = x;
    jos[i].y = y1;
  }
}

double semn (pct A, pct B, pct C) {
  return A.x * B.y - A.x * C.y - A.y * B.x + A.y * C.x + B.x * C.y - B.y * C.x;
}

bool comp(const pct &A, const pct &B) {
  if (A.x < B.x) return true;
  if (A.x > B.x) return false;
  return A.y < B.y;
}

void convex_hull(pct v[N], int st[N]) {
  for (int i = 1; i<= n; ++ i)
    f[i] = false;

  sort(v + 1, v + n + 1, comp);

  st[++ st[0]] = 1;
  f[1] = true;
  st[++ st[0]] = 2;
  f[2] = true;

  for (int i = 3; i <= n; ++ i) {
    while (semn(v[st[st[0]]], v[st[st[0] - 1]], v[i]) < 0 && st[0] > 1) {
      f[st[st[0]]] = false;
      -- st[0];
    }

    st[++ st[0]] = i;
    f[i] = true;
  }

  for (int i = n; i >= 1; -- i)
    if (! f[i] || i == 1) {
      while (semn(v[st[st[0]]], v[st[st[0] - 1]], v[i]) < 0 && st[0] > 1) {
        f[st[st[0]]] = false;
        -- st[0];
      }

      st[++ st[0]] = i;
      f[i] = true;
    }

    -- st[0];
}

inline double dist(pct A, pct B) {
  return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}

inline double unghi_Ox(pct A, pct B) {
  double u = asin((B.y - A.y) / dist(A, B)) / M_PI * 180;

  //centru xOy = (A.x, A.y)

  //cadran 1
  if (B.x >= A.x && B.y >= A.y)
    return u;

  //cadran 2
  if (B.x <= A.x && B.y >= A.y)
    return (double)180 - u;

  //cadran 3
  if (B.x <= A.x && B.y <= A.y)
    return (double)180 - u;

  //cadran 4
  return (double)360 + u;
}

inline double unghi_Oy(pct A, pct B) {
  double uOx = unghi_Ox(A, B);

  //centru xOy = (A.x, A.y)

  //partea superioara a infasuratorii => B.x >= A.x => doar cadranele 1 si 4

  //cadran 1
  if (B.y >= A.y)
    return (double)90 - uOx;

  //cadran 4
  return (double)360 - uOx;
}

inline pct rotire(pct A, double u) {
  double ur = u / 180 * M_PI; //unghi in rad
  double c = cos(ur), s = sin(ur);
  double x1 = (double)A.x * c, x2 = - (double)A.y * s;
  double y1 = (double)A.x * s, y2 = (double)A.y * c;
  double nx = x1 + x2, ny = y1 + y2;

  return (pct){nx, ny};
}

bool verifdr(pct A, double &max, pct O) {
  if (A.x >= O.x + eps) {
    if (A.x - O.x >= max) {
      max = A.x - O.x;
      return true;
    }
    return false;
  }

  return true;
}

bool verifst(pct A, double &max, pct O) {
  if (A.x <= O.x - eps) {
    if (O.x - A.x >= max) {
      max = O.x - A.x;
      return true;
    }
    return false;
  }

  return true;
}

bool solvedr()  {
  double uc = unghi_Oy(jos[stj[1]], jos[stj[2]]);

  pct pc, A = rotire(jos[stj[1]], uc);

  int it = 0;

  double maxdr = - 1;

  for (int j = 1; j <= sts[0]; ++ j) {
    pc = rotire(sus[sts[j]], uc);

    if (pc.x >= A.x + eps) {
      if (pc.x - A.x > maxdr) {
        maxdr = pc.x - A.x;
        it = j;
      }
    }
  }

  if (maxdr == - 1) {
    printf("%.0lf %.0lf %.0lf %.0lf\n", jos[stj[1]].x, jos[stj[1]].y, jos[stj[2]].x, jos[stj[2]].y);
    return true;
  }


  for (int i = 2; ; ++ i) {
    if (stj[i] == n)
      break;

    uc = unghi_Oy(jos[stj[i]], jos[stj[i + 1]]);

    A = rotire(jos[stj[i]], uc);

    pc = rotire(sus[sts[it]], uc);
    maxdr = - 1;
    if (pc.x >= A.x + eps)
      maxdr = pc.x - A.x;

    int qr = 0;

    while (verifdr(rotire(sus[sts[it + 1]], uc), maxdr, A) && it <= sts[0]) {
      ++ it;
      if (it > sts[0]) {
        it = 1;
        if (qr == 1)
            break;
        ++ qr;
      }
    }

    if (maxdr == - 1) {
      printf("%.0lf %.0lf %.0lf %.0lf\n", jos[stj[i]].x, jos[stj[i]].y, jos[stj[i + 1]].x, jos[stj[i + 1]].y);
      return true;
    }
  }

  return false;
}

bool solvest()  {
  double uc = unghi_Oy(sus[sts[1]], sus[sts[sts[0]]]);

  pct pc, A = rotire(sus[sts[1]], uc);

  int it = 0;

  double maxst = - 1;

  for (int j = 1; j <= stj[0]; ++ j) {
    pc = rotire(jos[stj[j]], uc);

    if (pc.x <= A.x - eps) {
      if (A.x - pc.x > maxst) {
        maxst = A.x - pc.x;
        it = j;
      }
    }
  }

  if (maxst == - 1) {
    printf("%.0lf %.0lf %.0lf %.0lf\n", sus[sts[1]].x, sus[sts[1]].y, sus[sts[sts[0]]].x, sus[sts[sts[0]]].y);
    return true;
  }


  for (int i = sts[0] - 1; ; -- i) {
    if (sts[i + 1] == n)
      break;

    uc = unghi_Oy(sus[sts[i + 1]], sus[sts[i]]);

    A = rotire(sus[sts[i]], uc);

    pc = rotire(jos[stj[it]], uc);
    maxst = - 1;
    if (pc.x <= A.x - eps)
      maxst = A.x - pc.x;

    int qr = 0;

    while (verifst(rotire(jos[stj[it + 1]], uc), maxst, A) && it <= stj[0]) {
      ++ it;
      if (it > stj[0]) {
        it = 1;
        if (qr == 1)
            break;
        ++ qr;
      }
    }

    if (maxst == - 1) {
        printf("%.0lf %.0lf %.0lf %.0lf\n", sus[sts[i]].x, sus[sts[i]].y, sus[sts[i + 1]].x, sus[sts[i + 1]].y);
        return true;
    }
  }

  return false;
}

int main() {
  freopen("oypara.in", "r", stdin);
  freopen("oypara.out", "w", stdout);

  read();

  convex_hull(sus, sts);

  convex_hull(jos, stj);

  if (! solvedr())
    solvest();

  return 0;
}