Cod sursa(job #1713712)

Utilizator atatomirTatomir Alex atatomir Data 6 iunie 2016 11:47:14
Problema Oypara Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

#define ll long long
#define mp make_pair

#define maxN 100011

struct Line {
    int x, y1, y2;

    bool operator<(const Line& who)const {
        return x < who.x;
    }
};

int n, i;
Line L[maxN];
double fy, ly;

double check(double y) {
    int i;
    double down = -5;
    double up = 5;

    for (i = 2; i <= n; i++){
        down = max(down, atan2(L[i].y1 - y, L[i].x - L[1].x));
        up = min(up, atan2(L[i].y2 - y, L[i].x - L[1].x));
    }

    ly = (up + down) /2.00;
    return up - down;
}

double aprox(double x) {
    if (x - floor(x) <= 0.50)
        x = floor(x);
    else
        x = ceil(x);

    return x;
}

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

    scanf("%d", &n);
    for (i = 1; i <= n; i++) {
        scanf("%d%d%d", &L[i].x, &L[i].y1, &L[i].y2);
        if (L[i].y1 > L[i].y2) swap(L[i].y1, L[i].y2);
    }

    sort(L + 1, L + n + 1);

    double l = L[1].y1;
    double r = L[1].y2;
    double m1, m2;
    int step = 10;

    while (step--) {
        m1 = (2 * l + r) / 3.00;
        m2 = (l + 2 * r) / 3.00;

        if (check(m1) < check(m2))
            l = m1;
        else
            r = m2;
    }

    fy = (l + r) / 2.00;
    fy = aprox(fy);

    ly = fy + tan(ly) * (L[n].x - L[1].x);
    ly = aprox(ly);



    printf("%d %d %d %d", L[1].x, (int)fy, L[n].x, (int)ly);

    return 0;
}