Pagini recente » Cod sursa (job #1699603) | Cod sursa (job #2732935) | Cod sursa (job #3005633) | Cod sursa (job #1674898) | Cod sursa (job #1155013)
#include <fstream>
#include <cstdio>
#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;
freopen("oypara.in","r",stdin);
scanf("%d\n",&n);
for(int i =1 ;i <= n; ++i){
int x ,y0 ,y1;
scanf("%d %d %d\n",&x,&y0,&y1);
Up.push_back(make_pair(x,y1));
Down.push_back(make_pair(x,y0));
}
}
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;
use = 0;
vector < int > stack1;
stack1.push_back(0);stack.push_back(v[0]);
int ok = 1 ;
int top = 0;
for(int i = 1;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;
++top;
}
if(i == n-1)
ok = -1;
}
}
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 && v1[i]!=v1[i+1]){
Sol1 = v1[i];
Sol2 = v1[i+1];
}
}
}
inline void Solve(){
ConvexHull(Up,Up.size(),v1);
ConvexHull(Down,Down.size(),v2);
Sol1.fi = INF;
Find(v2,v1,0);
Find(v1,v2,1);
}
inline void Write(){
ofstream g("oypara.out");
g<<Sol1.fi<<" "<<Sol1.se<<" "<<Sol2.fi<<" "<<Sol2.se<<"\n";
g.close();
}
int main(){
Read();
Solve();
Write();
return 0;
}