Cod sursa(job #1568824)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 14 ianuarie 2016 18:54:50
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 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.second - a.second) - (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].first < V[poz].first || (V[i].first == V[poz].first && V[i].second < V[poz].second))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 >= 1;i--)printf("%lf %lf\n",S[i].first,S[i].second);
    printf("\n");

    return 0;
}