Cod sursa(job #1881589)

Utilizator cella.florescuCella Florescu cella.florescu Data 16 februarie 2017 16:40:15
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda cerculdeinfo-lectiile9_10_11_12_13 Marime 1.01 kb
#include <cstdio>
#include <algorithm>
#define MAXN 120000

struct punct{
  double x, y;
} v[MAXN], stiv[MAXN], aux;

double cp(punct A, punct B, punct C){
  return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}

int cmp(punct A, punct B){
  return cp(v[0], A, B)>0;
}

int main(){
    FILE *fin, *fout;
    int n, i, p, st;
    fin=fopen("infasuratoare.in", "r");
    fscanf(fin, "%d", &n);
    for(i=0; i<n; i++)
      fscanf(fin, "%lf%lf", &v[i].x, &v[i].y);
    fclose(fin);
    p=0;
    for(i=1; i<n; i++)
      if(v[i].y<v[p].y || (v[i].y==v[p].y && v[i].x<v[p].x))
        p=i;
    aux=v[p]; v[p]=v[0]; v[0]=aux;
    std::sort(v+1, v+n, cmp);
    stiv[0]=v[0]; stiv[1]=v[1]; st=1;
    for(i=2; i<n; i++){
      while(st>=1 && cp(stiv[st-1], stiv[st], v[i])<0)
        --st;
      stiv[++st]=v[i];
    }
    fout=fopen("infasuratoare.out", "w");
    fprintf(fout, "%d\n", st+1);
    for(i=0; i<=st; i++)
      fprintf(fout, "%lf %lf\n", stiv[i].x, stiv[i].y);
    fclose(fout);
    return 0;
}