Pagini recente » Cod sursa (job #2297528) | Cod sursa (job #388464) | Cod sursa (job #2569249) | Cod sursa (job #2142871) | Cod sursa (job #1154219)
#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;
}