Cod sursa(job #1240323)

Utilizator enedumitruene dumitru enedumitru Data 11 octombrie 2014 00:50:54
Problema Oypara Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
#include <vector>
#include <algorithm>
#define x first
#define y second
#define mp make_pair
#define LL long long
#define per pair<LL,LL>
using namespace std;
vector <per> sus,jos,ls,lj;
LL det(per a,per b, per c) {return b.x*c.y+c.x*a.y+a.x*b.y-a.x*c.y-c.x*b.y-b.x*a.y<=0LL;}
vector <per> convexa(vector <per> p,int s)
{	sort(p.begin(),p.end());
	if(s) reverse(p.begin(),p.end());
	vector <per> st;
	st.push_back(p[0]); st.push_back(p[1]);
	for(int i=2;i<p.size();++i) 
	{	for(;st.size()>1 && det(st[st.size()-2],st[st.size()-1],p[i]);st.pop_back());
		st.push_back(p[i]);
	}
	return st;
}
per p1;
int main()
{   ifstream f("oypara.in"); ofstream g("oypara.out");
    int n; f>>n;
    for(int i=1; i<=n; ++i) 
	{	int x,y1,y2;
		f>>x>>y1>>y2;
		jos.push_back(mp(x,y1));
		sus.push_back(mp(x,y2));
    }
    lj=convexa(jos,1); ls=convexa(sus,0);
    for(int i=0,j=0;i+1<ls.size();++i) 
	{	for(;det(ls[i],ls[i+1],lj[j]) && j<lj.size();++j);
		if(j==lj.size()) {p1=ls[i]; break;}
    }
    for(int i=0;i+1<lj.size();++i) 
	{	if(det(lj[i],lj[i+1],p1)) 
		{	g<<p1.x<<' '<<p1.y<<' '<<lj[i].x<<' '<<lj[i].y;
			return 0;
		}
    }
    return 0;
}