Cod sursa(job #1155013)

Utilizator narcis_vsGemene Narcis - Gabriel narcis_vs Data 26 martie 2014 16:10:08
Problema Oypara Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
#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;
}