Cod sursa(job #1863598)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 31 ianuarie 2017 00:48:07
Problema Oypara Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.27 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;
char Str[60];
void Read()
{
    f >> N;
    f.get();
    for(int i = 1; i <= N; i++)
    {
        f.getline(Str, 60);
        int cnt = 0, val = 0;
        int x, y1, y2 = -1;
        for(int j = 0; Str[j] != 0; j++)
        {
            if(Str[j] >= '0' && Str[j] <= '9')
                val = val * 10 + Str[j] - '0';
            if(Str[j] == ' ')
            {
                ++cnt;
                if(cnt == 1)
                    x = val;
                if(cnt == 2)
                    y1 = val;
                if(cnt == 3)
                    y2 = val;
                val = 0;
            }
        }
        if(y2 == -1)
            y2 = val;
        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];
    }
}
inline 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;
    if(sign > 0)
        sign = 1;
    if(sign2 < 0)
        sign2 = -1;
    if(sign2 > 0)
        sign2 = 1;
    return sign == sign2 || sign == 0 || sign2 == 0;
}
inline 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;
    if(sign > 0)
        sign = 1;
    if(sign2 < 0)
        sign2 = -1;
    if(sign2 > 0)
        sign2 = 1;
    return sign == sign2 || sign == 0 || sign2 == 0;
}
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 = 1;
    for(int i = top[1]; i >= 1; i--)
    {
        while(j <= top[0] && check(i, j) == 0)
            ++j;
        if(j <= top[0] && check2(i, j) == 1 && S[0][j].first != S[1][i].first)
        {
            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;
}