Cod sursa(job #194212)

Utilizator filipbFilip Cristian Buruiana filipb Data 8 iunie 2008 21:40:20
Problema Oypara Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.13 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define ll long long
#define NMax 100005
#define PII pair<int, int>
#define x first
#define y second

typedef PII poligon[NMax];

int N, i1, i2;
poligon P1, P2, AUX; int sz[2];

int cmp(PII const& a, PII const& b)
{
    if (a.y != b.y)
        return a.y < b.y;
    return a.x < b.x;
}

inline int semn(PII p1, PII p2, PII p3)
{
    ll A = p1.y - p2.y, B = p2.x - p1.x, C = (ll)p1.x*p2.y - (ll)p2.x*p1.y;
    ll E = A * p3.x + B * p3.y + C;

    if (E > 0) return +1;
    if (E < 0) return -1;
    return 0;
}

int uz[NMax], st[NMax];
void ConvexHull(poligon P, int &size)
{
    int i, k, pas = +1;
    
    sort(P, P+N+1, cmp);
    
    for (i = 1; i <= N; ++i)
        uz[i] = 0;
        
    uz[2] = 1; st[1] = 1; st[k = 2] = 2; i = 2;
    for (; !uz[1]; )
    {
        while (uz[i])
        {
            i += pas;
            if (i == N)
                pas = -1;
        }
        while (k >= 2 && semn(P[st[k-1]], P[st[k]], P[i]) < 0)
            uz[st[k--]] = 0;
        uz[st[++k] = i] = 1;
    }
    
	for (i = 1; i <= N; ++i)
		AUX[i] = P[i];
    for (i = 1, size = 0; i <= k; ++i)
		P[++size] = AUX[st[i]];
	P[0] = P[--size];
}

inline bool intersect_poly1(PII p1, PII p2, int ii1, int ii2)
{ return semn(p1, p2, P1[ii1]) * semn(p1, p2, P1[ii2]) < 0; }

inline bool intersect_poly2(PII p1, PII p2, int ii1, int ii2)
{ return semn(p1, p2, P2[ii1]) * semn(p1, p2, P2[ii2]) < 0; }

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

    scanf("%d", &N);
    for (i = 1; i <= N; ++i)
    {
        scanf("%d %d %d", &P1[i].x, &P1[i].y, &P2[i].y);
        P2[i].x = P1[i].x;
    }

    ConvexHull(P1, sz[0]);
    ConvexHull(P2, sz[1]);
    
	for (i1 = 1, i = 2; i <= N; ++i)
		if (P1[i].x < P1[i1].x)
			i1 = i;
	for (i2 = 1, i = 2; i <= N; ++i)
		if (P2[i].x > P2[i2].x)
			i2 = i;
	for (; intersect_poly1(P1[i1], P2[i2], i1-1, i1+1); )
		i1 == 1 ? i1 = sz[0] : (--i1);
	for (; intersect_poly2(P1[i1], P2[i2], i2-1, i2+1); )
		i2 == 1 ? i2 = sz[1] : (--i2);
	
	printf("%d %d %d %d\n", P1[i1].x, P1[i1].y, P2[i2].x, P2[i2].y);
	
    return 0;
}