Cod sursa(job #1863567)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 30 ianuarie 2017 23:47:41
Problema Oypara Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.61 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("oypara.in");
ofstream g("oypara.out");
int N;
const int NMax = 100005;
pair <int, int> P[2][NMax], S[2][NMax];
int top[2];
int ind;
void Read()
{
    f >> N;
    for(int i = 1; i <= N; i++)
    {
        int x, y1, y2;
        f >> x >> y1 >> y2;
        P[0][i] = make_pair(x, y2);
        P[1][i] = make_pair(x, y1);
    }
}

inline long long Area(pair <int, int> a, pair <int, int> b, pair <int, int> c)
{
    return 1LL * a.first * b.second + 1LL * b.first * c.second + 1LL * c.first * a.second - 1LL * a.second * b.first - 1LL * b.second * c.first - 1LL * c.second * a.first;
}

inline bool cmp(pair <int, int> a, pair <int, int> b)
{
    long long area = Area(P[ind][1], a, b);
    if(area == 0)
        return a < b;
    return area > 0;
}

void Graham()
{
    pair <int, int> Min = make_pair(0x3f3f3f3f, 0x3f3f3f3f);
    int PMin = 1;
    for(int i = 1; i <= N; i++)
    {
        if(P[ind][i] < Min)
        {
            Min = P[ind][i];
            PMin = i;
        }
    }
    swap(P[ind][PMin], P[ind][1]);
    sort(P[ind] + 2, P[ind] + N + 1, cmp);
    top[ind] = 0;
    S[ind][++top[ind]] = P[ind][1];
    for(int i = 2; i <= N; i++)
    {
        while(top[ind] > 1 && Area(P[ind][i], S[ind][top[ind]], S[ind][top[ind] - 1]) >= 0)
            --top[ind];
        S[ind][++top[ind]] = P[ind][i];
    }
}
bool check(int i, int j)
{
    long long sign = Area(S[1][i], S[0][j], S[0][j - 1]), sign2 = Area(S[1][i], S[0][j], S[0][j + 1]);
    if(sign < 0)
        sign = -1;
    else
        sign = 1;
    if(sign2 < 0)
        sign2 = -1;
    else
        sign2 = 1;
    return sign == sign2;
}
bool check2(int i, int j)
{
    long long sign = Area(S[0][j], S[1][i], S[1][i - 1]), sign2 = Area(S[0][j], S[1][i], S[1][i + 1]);
    if(sign < 0)
        sign = -1;
    else
        sign = 1;
    if(sign2 < 0)
        sign2 = -1;
    else
        sign2 = 1;
    return sign == sign2;
}
void Solve()
{
    S[0][0] = S[0][top[0]];
    S[1][0] = S[1][top[1]];
    S[0][++top[0]] = S[0][1];
    S[1][++top[1]] = S[1][1];
    int j = top[0];
    for(int i = 1; i <= top[1]; i++)
    {
        while(j >= 1 && (S[1][i].first == S[0][j].first || check(i, j) == 0))
            --j;
        if(j > 0 && check2(i, j) == 1)
        {
            g << S[1][i].first << " " << S[1][i].second << " " << S[0][j].first << " " << S[0][j].second << "\n";
            break;
        }
    }
}
int main()
{
    Read();
    ind = 0;
    Graham();
    ind++;
    Graham();
    Solve();
    return 0;
}