Cod sursa(job #1567859)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 13 ianuarie 2016 19:46:26
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <cstdio>
#include <vector>
#define nmax 120004
#include <algorithm>

using namespace std;

typedef pair<double,double> Punct;
Punct V[nmax],S[nmax];
int N;

void interschimba(Punct &a,Punct &b){
  Punct aux = a;
  a = b;
  b = aux;
}

inline double produsX(const Punct &a,const Punct &b,const Punct &c){
   return (b.first - a.first) * (c.first - a.first) - (b. second - a.second) * (c.first - a.first);
}

inline bool cmp(const Punct &a,const Punct &b){
   return produsX(V[1],a,b) < 0;
}

int main(){

    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d ",&N);
    int i,poz;
    for(i = 1;i <= N;i++){
      scanf("%lf %lf",&V[i].first,&V[i].second);
      if(i == 1 || V[i] < V[poz])poz = i;
    }

    interschimba(V[1],V[poz]);
    sort(V + 2,V + N + 1,cmp);
    int h = 2;
    S[1] = V[1];
    S[2] = V[2];
    for(i = 3;i <= N;i++){
      while(h >= 2 && produsX(S[h-1],S[h],V[i]) > 0)--h;
      S[++h] = V[i];
    }

    printf("%d\n",h);
    for(i = h;i > 0;i--)printf("%lf %lf\n",S[i].first,S[i].second);
    printf("\n");

    return 0;
}