Cod sursa(job #1805608)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 13 noiembrie 2016 23:19:33
Problema Oypara Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;

const int SPQR = 100005;

struct PTX {
    int x, y;

    bool operator < (const PTX &arg) const {
        return (x == arg.x) ? (y < arg.y) : (x < arg.x); } };

int n, p0, p1;
vector<PTX> pts[2], hull[2];

inline i64 ccw(const PTX &a, const PTX &b, const PTX &c) {
    return i64(b.x - a.x) * (c.y - a.y) - i64(c.x - a.x) * (b.y - a.y); }

void make_hulls(void) {
    sort(pts[0].rbegin(), pts[0].rend()); // hai sa nu mai vorbim despre cum nu stiu eu sa bag rotating callipers
    sort(pts[1].begin(), pts[1].end());

    for(int i = 0; i < pts[0].size(); ++i) {
        while(hull[0].size() > 1 && ccw(hull[0][hull[0].size() - 2], hull[0][hull[0].size() - 1], pts[0][i]) <= 0)
            hull[0].pop_back();
        hull[0].push_back(pts[0][i]); }

    for(int i = 0; i < pts[1].size(); ++i) {
        while(hull[1].size() > 1 && ccw(hull[1][hull[1].size() - 2], hull[1][hull[1].size() - 1], pts[1][i]) <= 0)
            hull[1].pop_back();
        hull[1].push_back(pts[1][i]); } }

void get_calipers(void) { // mda...
    for(p0 = p1 = 0; p1 + 1 < hull[1].size(); ++p1) {
        for(; p0 < hull[0].size() && ccw(hull[1][p1], hull[1][p1 + 1], hull[0][p0]) <= 0; ++p0);
        if(p0 == hull[0].size())
            break; }

    for(p0 = 0; p0 + 1 < hull[0].size(); ++p0)
        if(ccw(hull[0][p0], hull[0][p0 + 1], hull[1][p1]) <= 0)
            break; }

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

    scanf("%d", &n);
    pts[0].resize(n);
    pts[1].resize(n);

    for(int i = 0; i < n; ++i) {
        scanf("%d%d%d", &pts[0][i].x, &pts[0][i].y, &pts[1][i].y);
        pts[1][i].x = pts[0][i].x; }

    make_hulls();
    get_calipers();

    printf("%d %d %d %d\n", hull[0][p0].x, hull[0][p0].y , hull[1][p1].x, hull[1][p1].y); //facepalm

    return 0; }