Cod sursa(job #408183)

Utilizator PetrucciDascal Cezar Petrucci Data 2 martie 2010 21:27:04
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <cstdio>
#include <algorithm>
using namespace std;
typedef struct punct{
        double x,y;
        };
const int NMAX=120021;
punct a[NMAX],O;
int N,M,s[NMAX];
double prod_vec(punct O,punct A,punct B){
      return (A.x-O.x)*(B.y-O.y)-(B.x-O.x)*(A.y-O.y);
      }
int cmp(punct A,punct B){
    return prod_vec(O,A,B)>0;
    }
int main(){
    int i,j;
    freopen("infasuratoare.in","r",stdin);  
    freopen("infasuratoare.out","w",stdout);  
    scanf("%d",&N);
    scanf("%lf %lf",&a[1].x,&a[1].y);
    O=a[1];j=1;
    for (i=2;i<=N;++i){
      scanf("%lf %lf",&a[i].x,&a[i].y);
      if (a[i].y<O.y || (a[i].y==O.y && a[i].x<O.x))
        O=a[i],j=i;}
    punct aux=a[1];a[1]=a[j];a[j]=aux;
    sort(a+2,a+N+1,cmp);
    M=2;s[1]=1;s[2]=2;
    for (i=3;i<=N;++i){
      while (M>=2 && prod_vec(a[s[M]],a[i],a[s[M-1]])<=0) M--;
      s[++M]=i;
      }
    printf("%d\n",M);
    for (i=1;i<=M;++i)
      printf("%lf %lf\n",a[s[i]].x,a[s[i]].y);         
    return 0;
}