Cod sursa(job #1240309)

Utilizator enedumitruene dumitru enedumitru Data 11 octombrie 2014 00:05:00
Problema Oypara Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 kb
#include<cstdio>
#include<vector>
#include<algorithm>
#define DIM 100010
#define x first
#define y second
#define pb push_back
#define mp make_pair
using namespace std;
vector < pair<int, int> > P,Q;
pair <int, int> S[DIM],aux;
long long det(const pair<int, int> &a, const pair<int, int> &b, const pair<int, int> &c) 
{	return (1LL*b.x-a.x)*(c.y-a.y) - (1LL*c.x-a.x)*(b.y-a.y);}
int cmp(const pair<int, int> &a, const pair<int, int> &b) 
{	return det(aux,a,b)>0;}
void infasuratoare(vector< pair<int, int> > &P)
{   int p=0;
    for(int j=0;j<P.size();j++)
        if(P[j].x<P[p].x || (P[j].x==P[p].x && P[j].y<P[p].y)) p=j;
    aux = P[p]; P[p] = P[0]; P[0] = aux;
    sort(P.begin()+1,P.end(),cmp);
    S[1]=P[0]; S[2]=P[1];
    int k=2;
    for(int j=2;j<P.size();j++) 
	{   while(k>=2 && det(S[k-1],S[k],P[j])<=0) k--;
        S[++k]=P[j];
    }
    P.clear();
    while(k) P.pb(S[k--]);
}
inline int next(vector< pair<int, int> > &P, int c)
{	return ((c!=P.size()-1) ? c+1 : 0);}
inline int prev(vector< pair<int, int> > &P, int c) 
{	return ((c==0) ? P.size()-1 : c-1);}
int okSus(int cp, int cq)
{   if(P[cp].x<Q[cq].x) 
		 {	if((det(P[cp],Q[cq],Q[prev(Q,cq)])>=0) && (det(P[cp],Q[cq],Q[next(Q,cq)])>=0)) return 1;} 
	else {	if((det(P[cp],Q[cq],Q[prev(Q,cq)])<=0) && (det(P[cp],Q[cq],Q[next(Q,cq)])<=0)) return 1;}
    return 0;
}
int okJos(int cp, int cq) 
{   int nxt, prv;
    if(P[cp].x<Q[cq].x) 
		 {	if(det(Q[cq],P[cp],P[nxt=next(P,cp)])>=0 && det(Q[cq],P[cp],P[prv=prev(P,cp)])>=0) return 1;} 
	else {	if(det(Q[cq],P[cp],P[nxt=next(P,cp)])<=0 && det(Q[cq],P[cp],P[prv=prev(P,cp)])<=0) return 1;}
    return 0;
}
int main()
{   freopen("oypara.in","r",stdin);
	int n,cp,cq;
	scanf("%d",&n);
    for(int u,v,w,i=1;i<=n;i++) 
		{scanf("%d%d%d",&u,&v,&w); P.pb(mp(u,v)); Q.pb(mp(u,w));}
    infasuratoare(P); infasuratoare(Q);
    cp=P.size()-1; cq=0;
    do {	if(okSus(cp,cq)) break; else cq=prev(Q,cq);} while(1);
    do {	if(okJos(cp,cq)) break;
			cp=next(P,cp);
			do 	{	if(okSus(cp,cq)) break; else cq=prev(Q,cq);} while(1);
			if(cp==P.size()-1) break;
		} 
	while(1);
	freopen("oypara.out","w",stdout);
    printf("%d %d %d %d\n",P[cp].x,P[cp].y,Q[cq].x,Q[cq].y);
    return 0;
}