Cod sursa(job #193644)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 5 iunie 2008 21:33:12
Problema Oypara Scor Ascuns
Compilator cpp Status done
Runda Marime 2.48 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>
#define nmax 100111
#define kmax 100111
#define sch(x,y) (x^=y^=x^=y)
#define EPS 1e-10

using namespace std;

typedef long long lint;

struct pct
{
  int x,y;  
};

char s[100];
int poz;

int n,k;

struct seg
{
  pct A,B;
}P[nmax],P1[kmax],P2[kmax];

int intre(double a,double b,double c)
{
  return(a-EPS<b&&b<c+EPS);   
}

int test(seg d)
{
  int i;
  if(d.A.x==d.B.x)
    return(0);
  double a=(double)(d.A.y-d.B.y)/(d.A.x-d.B.x);
  for(i=1;i<=n;++i)
    if(!intre(P[i].A.y, d.A.y+a*(P[i].A.x-d.A.x) ,P[i].B.y))
      return(0);
  return(1);
}

int semn(pct A,pct B)
{
  lint aux=((lint)A.x)*B.y-((lint)A.y*B.x);
  return(aux>0?1:(aux?-1:0));
}

bool cmp1(const seg i,const seg j)
{
//  return(atan2(i.A.y,i.A.x)+EPS<atan2(j.A.y,j.A.x));
  return(semn(i.A,j.A)>0);
}

bool cmp2(const seg i,const seg j)
{
  return(semn(i.B,j.B)<0);
//  return(atan2(i.B.y,i.B.x)-EPS>atan2(j.B.y,j.B.x));
}

bool cmp3(const seg i,const seg j)
{
  return(i.A.y>j.A.y||(i.A.y==j.A.y&&i.A.x<j.A.x));
}

bool cmp4(const seg i,const seg j)
{
  return(i.B.y>j.B.y||(i.B.y==j.B.y&&i.B.x<j.B.x));
}

seg solv()
{
  seg d;
  int i,j,k2=sqrt(1000*nmax/n);  
//  printf("%d\n",k2);
  if(k2>n)
    k2=n;  
  k=10;
  if(k>n)
    k=n;
  sort(P+1,P+n+1,cmp1);
  for(i=1;i<=n&&i<=k;++i)
    P1[i]=P[i];  
  P1[k]=P[n];
  sort(P+1,P+n+1,cmp3);
  for(i=1;i<=k2&&i<=n;++i)
    P1[i+k]=P[i];
  
  sort(P+1,P+n+1,cmp2);
  for(i=1;i<=n&&i<=k;++i)
    P2[i]=P[i];
  P2[k]=P[n];
  sort(P+1,P+n+1,cmp4);
  for(i=1;i<=k2&&i<=n;++i)
    P2[i+k]=P[i];
  
  k+=k2+1;
  P2[k]=P1[k]=P[0];
  for(i=1;i<=k;++i)
    for(j=1;j<=k;++j)
    {
      d.A=P1[i].A, d.B=P2[j].B;      
      if(test(d))
	return(d);      
    }  
}

int cit()
{
  int aux=0;
  for(;s[poz]<'0'||s[poz]>'9';poz++);
  for(aux=0;s[poz]>='0'&&s[poz]<='9';++poz)
    aux=aux*10+s[poz]-'0';
  return(aux);
}

int special()
{
  int i;
  for(i=2;i<=n;++i)
    if(P[i].A.x!=P[i-1].A.x)
      return(0);
  return(1);
}

int main()
{
  FILE *fi=fopen("oypara.in","r"),*fo=fopen("oypara.out","w");
  fgets(s,100,fi);poz=0;
  n=cit();
  int i;
  for(i=1;i<=n;++i)
  {
    fgets(s,100,fi);poz=0;
    P[i].A.x=P[i].B.x=cit();
    P[i].A.y=cit();
    P[i].B.y=cit();
    if(P[i].A.y>P[i].B.y)
      sch(P[i].A.y,P[i].B.y);      
  }  
  fclose(fi);
  if(special())
  {
    fprintf(fo,"%d %d %d %d\n",P[1].A.x,P[1].A.y,P[2].B.x,P[2].B.y);
    return(0);
  }
  seg sol=solv();
  fprintf(fo,"%d %d %d %d\n",sol.A.x,sol.A.y,sol.B.x,sol.B.y);
  fclose(fo);    
  return(0);
}