Cod sursa(job #1109157)

Utilizator danalex97Dan H Alexandru danalex97 Data 16 februarie 2014 19:35:50
Problema Oypara Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.5 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream F("oypara.in");
ofstream G("oypara.out");

const int N = 100010;

typedef pair<int,int> pii;
#define x first
#define y second
#define y1 second.first
#define y2 second.second

vector< pair<int,pii> > lines;
vector<pii> up,down;

bool ecu(pii A,pii B,pii C)
{
    int a = A.y - B.y;
    int b = B.x - A.x;
    long long c = - B.x * A.y + A.x * B.y;
    return ( 1LL * a * C.x + 1LL * b * C.y + c ) > 0;
}

long long ecu2(pii C,pii A,pii B)
{
    long long a = A.y - B.y;
    long long b = B.x - A.x;
    long long c = - a * A.x - b * A.y;
    return 1LL * a * C.x + 1LL * b * C.y + c;
}

vector<pii> parc(vector<pii> a,int l,int r)
{
    int step = l < r ? 1 : -1;
    vector<pii> out;
    for (int i=l;i!=(r+step);i+=step)
        if ( i == l || i == r || ecu(a[l],a[r],a[i]) == 1 )
        {
            out.push_back(a[i]);
            if ( out.size() > 2 )
                while ( ecu(out[int(out.size())-3],out[int(out.size())-1],out[int(out.size())-2]) == -1 )
                {
                    out[int(out.size())-2] = out[int(out.size())-1];
                    out.pop_back();
                    if ( out.size() <= 2 ) break;
                }
        }
    return out;
}

vector<pii> convex_hull(vector<pii> a)
{
    sort(a.begin(),a.end());
    vector<pii> out,stack;
    int n = a.size();
    stack = parc(a,0,n-1);
    for (int i=0;i<int(stack.size())-1;++i)
        out.push_back(stack[i]);
    stack = parc(a,n-1,0);
    for (int i=0;i<int(stack.size())-1;++i)
        out.push_back(stack[i]);
    //reverse(out.begin(),out.end());
    return out;
}

int main()
{
    int n = 0;
    F>>n;
    for (int i=1;i<=n;++i)
    {
        pair<int,pii> pt;
        F>>pt.x>>pt.y1>>pt.y2;
        lines.push_back( pt );
    }
    sort(lines.begin(),lines.end());
    for (int i=0;i<n;++i)
    {
        up.push_back( make_pair(lines[i].x,lines[i].y2) );
        down.push_back( make_pair(lines[i].x,lines[i].y1) );
    }
    up = convex_hull(up);
    down = convex_hull(down);

    int where = 0;
    for (int i=0;i<int(down.size());++i)
	{
	    while ( 1 )
		{
			int prev = where == 0 ? int(up.size())-1 : where-1;
			if ( ecu2(up[prev],down[i],up[where]) > 0 )
				break;
			where = prev;
		}
        while ( 1 )
		{
			int next = where == int(up.size())-1 ? 0 : where+1;
			if ( ecu2(up[next],down[i],up[where]) > 0 )
				break;
			where = next;
		}
		int next = i == int(down.size())-1 ? 0 : i+1;
		int prev = i == 0 ? int(down.size())-1 : i-1;
		if ( ecu2(down[next],down[i],up[where]) < 0 &&
             ecu2(down[prev],down[i],up[where]) < 0 )
		{
            G<<down[i].x<<' '<<down[i].y<<' ';
            G<<up[where].x<<' '<<up[where].y<<'\n';
			return 0;
		}
	}

    where = 0;
	for (int i=0;i<int(down.size());++i)
	{
		while ( 1 )
		{
			int next = where == int(up.size())-1 ? 0 : where+1;
			if ( ecu2(up[next],down[i],up[where]) < 0 )
				break;
			where = next;
		}
		while ( 1 )
		{
			int prev = where == 0 ? int(up.size())-1 : where-1;
			if ( ecu2(up[prev],down[i],up[where]) < 0 )
				break;
			where = prev;
		}
		int next = i == int(down.size())-1 ? 0 : i+1;
		int prev = i == 0 ? int(down.size())-1 : i-1;
		if ( ecu2(down[next],down[i],up[where]) > 0 &&
             ecu2(down[prev],down[i],up[where]) > 0 )
		{
            G<<down[i].x<<' '<<down[i].y<<' ';
            G<<up[where].x<<' '<<up[where].y<<'\n';
			return 0;
		}
	}
}