Cod sursa(job #251404)

Utilizator MciprianMMciprianM MciprianM Data 2 februarie 2009 15:39:38
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include<cstdio>
#include<algorithm>
using namespace std;
struct Punct {
  double x, y;
}a[120009];
int s[120009], ref;
int Stiva[120009],vf=-1;
int cmp(int a1, int b){
  return  ( (double) (a[a1].x-a[ref].x)*(a[b].y-a[ref].y))>
          ( (double) (a[b].x-a[ref].x)*(a[a1].y-a[ref].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[s[gh]].x+bb*a[s[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));
    if(a[ref].x>a[i].x||(a[ref].x==a[i].x&& a[ref].y>a[i].y))
      ref=i;
  }
  int l=1;
  for(i=0;i<n;i++)
    if(i!=ref)
      s[l++]=i;
  sort(s+1, s+n, cmp);
  s[0]=ref;
  Stiva[++vf]=s[0];
  Stiva[++vf]=s[1];
  for(i=2;i<n;i++){
    while(vf>0&&semn(i)=='-') Stiva[vf--];
    Stiva[++vf]=s[i];
  }
  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;
}