Cod sursa(job #338440)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 5 august 2009 19:48:26
Problema Oypara Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.18 kb
//O(nrp1*nrp2*n+n log n)

#include<stdio.h>  
#include<algorithm>  

  
using namespace std;  

FILE*fin=fopen("oypara.in","r");
FILE*fout=fopen("oypara.out","w");
  
const int INF = 2000000000;  

#define ll int
#define maxn 100005
  
ll X[maxn],Y[maxn];  

int PI,IND[maxn],ST[maxn],x1[maxn],y1[maxn];
int x2[maxn],y2[maxn],seg[maxn][3],n;  
  
bool cmpf(int i,int j)  
{  
    return (ll)(X[i] - X[PI]) * (Y[j] - Y[PI]) < (ll)(X[j] - X[PI]) * (Y[i] - Y[PI]);  
}  
  
ll semn(int i1,int i2,int i3)  
{  
    return (ll)X[i1] * Y[i2] + X[i2] * Y[i3] + X[i3] * Y[i1] - Y[i1] * X[i2] - Y[i2] * X[i3] - Y[i3] * X[i1];  
}  

int csemn(int a)
{
  if(a<0) return -1;
  if(a>0) return 1;
  return 0;
}
  
void conv_hull(int N,int w)  
{  
     
    memset(ST,0,sizeof(ST));
    memset(IND,0,sizeof(IND));
      
    X[0] = INF;Y[0] = INF;  
    int punct_initial = 0;  
    for(int i = 1;i <= N; ++i)  
    {  
        if (X[i] < X[punct_initial] || (X[i] == X[punct_initial] && Y[i] < Y[punct_initial])) punct_initial = i;  
    }  
    PI = punct_initial;  
    for(int i = 1;i <= N; ++i)  
    {  
        if (i == punct_initial) continue;   
        IND[++IND[0]] = i;  
    }  
    sort(IND + 1,IND + IND[0] + 1,cmpf);  
    ST[ST[0] = 1] = punct_initial;  
    for(int i = 1;i <= IND[0]; ++i)  
    {  
        if (IND[i] == punct_initial) continue;  
        while(ST[0] >= 2 && semn(ST[ST[0] - 1],ST[ST[0]],IND[i]) > 0) --ST[0];  
        ST[++ST[0]] = IND[i];  
    }  
    ST[++ST[0]] = punct_initial;  
    
    reverse(ST + 1, ST + ST[0] + 1);  
    for(int i = 1;i < ST[0]; ++i)  
    {  
         if(w)
         {
           x1[0]++;
           y1[0]++;
           x1[x1[0]]=X[ST[i]];
           y1[y1[0]]=Y[ST[i]];
         }   
         else
         {
           x2[0]++;
           y2[0]++;
           x2[x2[0]]=X[ST[i]];
           y2[y2[0]]=Y[ST[i]];
         }
    }  
}  

inline int bad(int xs1,int ys1,int xs2,int ys2,int xx1,int yy1,int xx2,int yy2)
{
    int a,b;
    
    a=csemn((ll)(xs1-xx1)*(yy2-yy1)-(ll)(ys1-yy1)*(xx2-xx1));
    b=csemn((ll)(xs2-xx1)*(yy2-yy1)-(ll)(ys2-yy1)*(xx2-xx1));
    
    if(a==b) return 1;
    return 0;
}

int main()
{
    int a,b,c,i,j,k;
    
    fscanf(fin,"%d",&n);
    
    for(i=1;i<=n;i++)
    {
      fscanf(fin,"%d%d%d",&a,&b,&c);
      seg[i][0]=a;
      seg[i][1]=b;
      seg[i][2]=c;
    }
    
    for(i=1;i<=n;i++)
    {
      X[i]=seg[i][0];
      Y[i]=seg[i][1];
    }
    
    conv_hull(n,0);
    
    for(i=1;i<=n;i++)
    {
      X[i]=seg[i][0];
      Y[i]=seg[i][2];
    }
    
    conv_hull(n,1);
    
    for(i=1;i<=x1[0];i++)
      for(j=1;j<=x2[0];j++)
      {
        int ok=1;                   
        for(k=1;k<=n;k++)
          if(bad(seg[k][0],seg[k][1],seg[k][0],seg[k][2],x1[i],y1[i],x2[j],y2[j])) 
          {
            ok=0;
            break;
          }
        if(ok)
        {
          fprintf(fout,"%d %d %d %d",x1[i],y1[i],x2[j],y2[j]);
          
          fclose(fin);
          fclose(fout);
    
          return 0;
        }  
      }
    
    fclose(fin);
    fclose(fout);
    
    return 0;
}