Cod sursa(job #251269)

Utilizator MciprianMMciprianM MciprianM Data 2 februarie 2009 10:08:37
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include<cstdio>
#include<algorithm>
using namespace std;
struct Punct {
  double x, y;
}a[120009];
int Stiva[120009],vf=-1;
bool viz[120009];
int cmp(Punct a, Punct b){
   if(a.y==b.y)
     return a.x<b.x;
   return a.y<b.y;
}
void coeficienti(Punct a, Punct b, double& aa, double& bb, double& cc){
  aa=a.y-b.y;
  bb=b.x-a.x;
  cc=b.y*a.x-b.x*a.y;
}
char semn(int gh){
  double aa, bb, cc;
  coeficienti(a[Stiva[vf-1]], a[Stiva[vf]], aa, bb, cc);
  if(aa*a[gh].x+bb*a[gh].y+cc>=0)
   return '+';
  return '-';
}
int main(){
  int i, n;
  freopen("infasuratoare.in","r",stdin);
  scanf("%d", &n);
  for(i=0;i<n;i++)
    scanf("%lf%lf",&(a[i].x), &(a[i].y));
  sort(a, a+n, cmp);
  Stiva[++vf]=0;
  Stiva[++vf]=1;
  viz[0]=1;
  viz[1]=1;
  for(i=2;i<n&&a[i].y>=a[i-1].y;i++){
    while(vf>0&&semn(i)=='-') viz[Stiva[vf--]]=0;
    viz[Stiva[++vf]=i]=1;
  }
  for(i=n-1;i>=0;i--)
    if(!viz[i]){
      while(vf>0&&semn(i)=='-') viz[Stiva[vf--]]=0;
      viz[Stiva[++vf]=i]=1;
    }
  while(semn(0)=='-')  --vf;
  freopen("infasuratoare.out","w",stdout);
  printf("%d\n",vf+1);
  for(i=0;i<=vf;i++){
    printf("%.6lf ",a[Stiva[i]].x);
    printf("%.6lf\n",a[Stiva[i]].y);
  }
  return 0;
}