Cod sursa(job #264454)

Utilizator nicolaetitus12Nicolae Titus nicolaetitus12 Data 22 februarie 2009 03:22:36
Problema Infasuratoare convexa Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <list>
using namespace std;
double x[120001];
double y[120001];
double cs[120001];
int id[120001];
void sort(int st,int dr)
{int s=st,d=dr,aux;
 double p=cs[id[st+rand()%(dr-st+1)]];
 while(s<d)
 {while(cs[id[s]]>p)s++;
  while(cs[id[d]]<p)d--;
  if(s<=d)
  {aux=id[s];id[s]=id[d];id[d]=aux;
   s++;
   d--;
  }
 }
 if(st<d)
  sort(st,d);
 if(s<dr)
  sort(s,dr);
}
int test(list<int> l)
{list<int>::iterator it1,it2,it3;
 it1=--l.end();
 it2=----l.end();
 it3=------l.end();
 return ((y[*it1]-y[*it2])*(x[*it3]-x[*it2])-(y[*it3]-y[*it2])*(x[*it1]-x[*it2]))>0.0;
}

int main ()
{freopen("infasuratoare.in","r",stdin);
 freopen("infasuratoare.out","w",stdout);
 int n,p,i;
 double y1,x1;
 list<int> l;
 list<int>::reverse_iterator itr;
 list<int>::iterator it;
 scanf("%d",&n);
 for (i=1,p=0,y1=1000000002.0;i<=n;i++)
 { scanf("%lf%lf",&x[i],&y[i]);
  if(y[i]<y1)
  {p=i;
   y1=y[i];
  }
 }
 x1=x[p];
 x[p]=x[n];
 y[p]=y[n];
 n--;
 for (i=1;i<=n;i++)
 {cs[i]=(x[i]-x1)/sqrt((x[i]-x1)*(x[i]-x1)+(y[i]-y1)*(y[i]-y1));}
 for (i=1;i<=n;i++)
  id[i]=i;
 sort(1,n);

 for (i=1;i<=n;i++)
 {while(l.size()>2&&test(l))
  {it=l.end();
   it--;it--;
   l.erase(it);
  }
  l.push_back(id[i]);
 }
 printf("%d\n",l.size()+1);
 printf("%lf %lf\n",x1,y1);
 for (it=l.begin();it!=l.end();it++)
 printf("%lf %lf\n",x[*it],y[*it]);
 return 0;
}