Cod sursa(job #193657)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 5 iunie 2008 22:34:23
Problema Oypara Scor Ascuns
Compilator cpp Status done
Runda Marime 3.71 kb
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

#define FOR(i, a, b) for (i = (a); i <= (b); i ++)
#define REP(i, n)    for (i =   0; i <  (n); i ++)
#define FORI(i, x)   for (i = (x).begin(); i != (x).end(); i ++)
#define mp make_pair
#define pb push_back
#define LL long long
#define LD long double
#define swap(x, y) ((x) ^= (y) ^= (x) ^= (y))

#define ZPI 3.1415

#define NMAX 100005
int x[NMAX], py1[NMAX], py2[NMAX];
int N, i, j, k, A1, B1, A2, B2, xA1, xB1;

void read(void)
{
    freopen("oypara.in", "r", stdin);
    freopen("oypara.out", "w", stdout);
    scanf("%d", &N);
    REP(i, N)
    {
        scanf("%d %d %d", &(x[i]), &(py1[i]), &(py2[i]));
        if (py1[i] > py2[i]) swap(py1[i], py2[i]);
    }
}

int check(int A1, int B1, int A2, int B2)
{
    register LL new_y, m, n, zy1, zy2;
    register int i;

    n = (LL)B1*(LL)A2 - (LL)B2*(LL)A1;
    m = B2 - B1;

    REP(i, N)
    {
        new_y = n + (LL)x[i] * m;
        zy1 = (LL)py1[i] * (LL)(A2 - A1);
        zy2 = (LL)py2[i] * (LL)(A2 - A1);

        if (!(zy1 <= new_y && new_y <= zy2))
            return 0;
    }
    return 1;
}

void gen_naspa(void)
{
    srand(24);
    freopen("oypara.in", "w", stdout);
    N = 100000;
    A1 = 1, B1 = 5, A2 = 100000, B2 = 1123452;

    printf("%d\n", N);
    int i;
    REP(i, N)
    {
        int x = 5 + rand() % 100000;
        LD y = ((LL)B1*(LL)A2 - (LL)B2*(LL)A1 + (LL)x * (LL)(B2 - B1)) / (LD)(A2 - A1);
        LL yy = (LL)y;

//        printf("%d %ld ", x, yy - 1);
//        printf("%ld\n", yy + 1);
        printf("%d %d %d\n", i + 1, 10, 11);
    }
}

#define INF 1.7E38
int get_ans(LD u)
{
    LD min_y2 = INF, max_y1 = -INF, zy1, zy2;
    LD cs = cos(u), sn = sin(u);
    int i, mn_i, mx_i;

    REP(i, N)
    {
        zy1 = x[i] * sn + py1[i] * cs;
        zy2 = x[i] * sn + py2[i] * cs;

        if (zy2 < min_y2) min_y2 = zy2, mn_i = i;
        if (zy1 > max_y1) max_y1 = zy1, mx_i = i;
    }

    if (max_y1 <= min_y2)   //am gasit
    {
//        printf("%d %d %d %d\n", x[mx_i], py1[mx_i], x[mn_i], py2[mn_i]);
//        printf(">>> %d\n", check(x[mx_i], py1[mx_i], x[mn_i], py2[mn_i]));
        A1 = x[mx_i], B1 = py1[mx_i];
        xA1 = x[mn_i], xB1 = py2[mn_i];
        return 0;
    }
    else
    {
        if (x[mx_i] > x[mn_i])
            return 1; //mai am de rotit
        else
            return -1; //am rotit prea mult
    }
}

void get(void)
{
    int ret;
    LD l, r, m;
    l = -ZPI / 2, r = ZPI / 2;
    for (;;)
    {
        m = (l + r) / 2;
        ret = get_ans(m);

        if (ret == 0)
            return;
        if (ret == -1)
            l = m;
        else
            r = m;
    }
}

void baga(int A1, int B1)
{
    int i, minA2, minB2, maxA2, maxB2, g_min = 0, g_max = 0;
    LD min_p = 1.7E38, max_p = -1.7E38, p;
    
    REP(i, N)
    {
        p = (LD)(py2[i] - B1) / (LD)(x[i] - A1);
        if (x[i] > A1)
        {
            if (p < min_p)
                min_p = p, minA2 = x[i], minB2 = py2[i], g_min = 1;
        }
        if (x[i] < A1)
        {
            if (p > max_p)
                max_p = p, maxA2 = x[i], maxB2 = py2[i], g_max = 1;
        }
    }

    if (g_min)
    {
        if (check(A1, B1, minA2, minB2))
        {
            printf("%d %d %d %d\n", A1, B1, minA2, minB2);
            exit(0);
        }
    }

    if (g_max)
    {
        if (check(A1, B1, maxA2, maxB2))
        {
            printf("%d %d %d %d\n", A1, B1, maxA2, maxB2);
            exit(0);
        }
    }
}


int main(void)
{
//gen_naspa();
//return 0;
    read();
    get();
    baga(A1, B1);
    A1 = xA1, B1 = xB1;
    baga(A1, B1);

//    printf("f");
    printf("%d %d %d %d\n", A1, B1, A2, B2); //this shouldn't happen
    return 0;
}