Cod sursa(job #1154234)

Utilizator narcis_vsGemene Narcis - Gabriel narcis_vs Data 26 martie 2014 01:11:58
Problema Oypara Scor 10
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.94 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <bitset>
#define fi first
#define se second
#define pii pair < int, int >
using namespace std ; 
const int NMAX = 100002;
const int INF = 0x3f3f3f3f;
vector < pii  > Up ,Down, v1 ,v2;
pii Sol1,Sol2;
inline void Read(){
	int n;
	ifstream f("oypara.in");
	f >> n ;
	for(int i =1 ;i <= n; ++i){
		int x ,y0 ,y1;
		f >> x >> y0 >> y1 ;
		Up.push_back(make_pair(x,y1));
		Down.push_back(make_pair(x,y0));
	}
	f.close();
}

inline int Det(const pii &a,const pii &b,const pii &c){
	long long  x = 1LL*(b.fi-a.fi)*(c.se-a.se);
	long long  y = 1LL*(b.se-a.se)*(c.fi-a.fi);
	if(x==y)
		return 0;
	if(x > y)
		return 1;
	return -1;
}

inline void ConvexHull(vector < pii > &v,const int&n,vector < pii > &stack){
	sort(v.begin(),v.end());
	bitset < NMAX > use; 
	vector < int> stack1;
	stack1.push_back(0);stack.push_back(v[0]);
	stack1.push_back(1);stack.push_back(v[1]);
	use[1] = 1;
	int ok = 1 ;
	int top = 1;
	for(int i = 2;i >= 0; i += ok){
		if(!use[i]){
			while(top > 0 &&  Det(stack[top-1],stack[top],v[i]) <= 0){
				stack.pop_back();
				use[stack1[top]] = 0;
				stack1.pop_back();
				--top;
			}
			stack.push_back(v[i]);
			stack1.push_back(i);
			use[i] = 1;
		}
		if(i == n-1)
			ok = -1;
	}
}
ofstream g("oypara.out");
inline void Find(const vector < pii > &v1,const vector < pii > &v2,const bool ok){
	int n = v1.size()-1;
	int m = v2.size()-1;
	int j = 0;
	for(int i = 0;Sol1.fi == INF && i <= n; ++i){
		if((v1[i] < v1[i+1])!= ok)
			continue;
		int cnt = 0;
		for( ; cnt <= m && Det(v1[i],v1[i+1],v2[j]) <= 0; j = (j+1)%m, ++cnt);
		if(cnt >= m){
			Sol1 = v1[i];
			Sol2 = v1[i+1];
			break;
		}
	}
}
inline void Solve(){
	ConvexHull(Up,Up.size(),v1);
	ConvexHull(Down,Down.size(),v2);
	Sol1.fi = INF;
	Find(v1,v2,1);
	Find(v2,v1,0);
}

inline void Write(){
	//ofstream g("oypara.out");
	g<<Sol1.fi<<" "<<Sol1.se<<" "<<Sol2.fi<<" "<<Sol2.se<<"\n";
}

int main(){
	Read();
	Solve();
	Write();
	return 0;
}