Cod sursa(job #1562067)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 4 ianuarie 2016 19:29:37
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <cstdio>
#include <algorithm>
#define nmax 120004

using namespace std;

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

void interschimba(Point &A,Point &B){

    Point C = A;
    A = B;
    B = C;

}

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

    int N;
    scanf("%d ",&N);
    int i,j,k = 1;

    for(i = 1;i <= N;++i){
        scanf("%lf %lf",&V[i].first,&V[i].second);
        if(V[i] < V[k])k = i;
    }

    interschimba(V[1],V[k]);
    sort(V+2,V+N+1,cmp);

    S[1] = V[1];
    S[2] = V[2];
    int H = 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 = 1;i <= H;++i)printf("%lf %lf\n",S[i].first,S[i].second);

    return 0;
}