Cod sursa(job #1560473)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 2 ianuarie 2016 19:17:59
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <cstdio>
#include <algorithm>
#define nmax 120003

using namespace std;

typedef pair<double,double> Point;
Point V[nmax],S[nmax];
int N,H = 2;

void schimba(Point &A,Point &B){
  Point aux = A;
  A = B;
  B = aux;
}

inline double produsX(const Point &A,const Point &B,const Point &C){
   return (B.first - A.first) * (C.second - A.second) - (B.second - A.second) * (C.first - A.first);
}

inline bool cp(const Point &A,const Point &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,p = 1;
    for(i = 1;i <= N;++i){
       scanf("%lf %lf",&V[i].first,&V[i].second);
       if(V[i] < V[p])p = i;
    }

    schimba(V[1],V[p]);
    sort(V+2,V+N+1,cp);

    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);

    return 0;
}