Cod sursa(job #455424)

Utilizator Bogdan_CCebere Bogdan Bogdan_C Data 13 mai 2010 19:24:42
Problema Oypara Scor 90
Compilator cpp Status done
Runda Lista lui wefgef Marime 3.22 kb
#include<stdio.h>
#include<algorithm>
#define FIN "oypara.in"
#define FOUT "oypara.out"
#define NMAX 100003
#define x first
#define y second
#define PR pair<int,int>
using namespace std;

PR S[NMAX],J[NMAX],ST[NMAX],JT[NMAX];
struct SEGM {int x,y1,y2;} PCT[NMAX];
int viz[NMAX] , stack[NMAX] , x , y1 ,y2 ,N;

bool  comp(SEGM a , SEGM b)
{
    return a.x < b.x;
    }

bool comp2( PR a, PR b )
{
      return a.x < b.x;
}

long long unghi ( PR a , PR b , PR c )
{
  return 1LL*(b.y - a.y) * (a.x - c.x) + 1LL * (a.y - c.y) * (a.x - b.x);  
    }    
 
void ConvexHull( PR P[] , PR RZ[] )
{
  int k = 2 , i = 3 , pas = 1;
  memset(viz , 0 ,  sizeof(viz));
  memset(stack , 0 , sizeof(stack));
  viz[1] = 0; viz[2] = 1;
  stack[1] = 1;stack[2] = 2;
  while(!viz[1])
  {
    while(viz[i])
     {
       if( i == N) pas = -1;
       i += pas;     
        }
    while(k >= 2 && unghi(P[stack[k-1]] , P[i] , P[stack[k]] ) < 0 )
     viz[stack[k--]] = 0;
     viz[stack[++k] = i] = 1;          
  }  
  RZ[0].x = k-1;
  for(int i = 1 ; i <= RZ[0].x ;i++)
   RZ[i] = P[stack[i]];
   
}    



int main()
{
  freopen(FIN,"r",stdin);
  freopen(FOUT,"w",stdout);
  scanf("%d",&N);
  for(int i = 1 ;i <= N ; i++)
    scanf("%d %d %d",&PCT[i].x,&PCT[i].y1,&PCT[i].y2); 
   sort(PCT+1 , PCT+N+1 , comp );
 
   for(int i = 1 ;i<=N ; i++)
    {
     ST[i].x = JT[i].x = PCT[i].x;
     ST[i].y = PCT[i].y2;
     JT[i].y = PCT[i].y1;}
   ConvexHull(ST,S);
   ConvexHull(JT,J);
   int raspuns = 1 , next , prev;  
   for(int i = 1 ; i <= J[0].x ; i++)
    {
      while(1)
       {
         if(raspuns == S[0].x) next = 1;
         else next = raspuns + 1;
         if( unghi( J[i] , S[raspuns] , S[next] ) >= 0 ) break;
         raspuns = next;   
            }  
      while(1)
       {
         if(raspuns == 1) prev = S[0].x;
         else prev = raspuns - 1;
         if( unghi( J[i] , S[raspuns] , S[prev] ) >= 0 ) break;
         raspuns = prev;   
            }      
        if(i == S[0].x ) next = 1;
        else next = i+1;
        if(i == 1 ) prev = S[0].x;
        else prev = i-1;   
       if( unghi( J[i] , J[prev],S[raspuns] ) >= 0 && unghi( J[i] , J[next],S[raspuns] ) >= 0)     
        {
          printf("%d %d %d %d\n",J[i].x,J[i].y,S[raspuns].x,S[raspuns].y);
          return 0;  
            }
        }
    raspuns = 1; 
    for(int i = 1 ; i <= J[0].x ; i++)
    {
      while(1)
       {
         if(raspuns == S[0].x) next = 1;
         else next = raspuns + 1;
         if( unghi( J[i] , S[raspuns] , S[next] ) <= 0 ) break;
         raspuns = next;   
            }  
      while(1)
       {
         if(raspuns == 1) prev = S[0].x;
         else prev = raspuns - 1;
         if( unghi( J[i] , S[raspuns] , S[prev] ) <= 0 ) break;
         raspuns = prev;   
            }      
        if(i == S[0].x ) next = 1;
        else next = i+1;
        if(i == 1 ) prev = S[0].x;
        else prev = i-1;   
       if( unghi( J[i] , J[prev],S[raspuns] ) <= 0 && unghi( J[i] , J[next],S[raspuns] ) <= 0)     
        {
          printf("%d %d %d %d\n",J[i].x,J[i].y,S[raspuns].x,S[raspuns].y);
          return 0;  
            }
        }      
   return 0;  
    }