Cod sursa(job #1506244)

Utilizator tudormaximTudor Maxim tudormaxim Data 20 octombrie 2015 11:46:42
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <iomanip>
using namespace std;

struct point{
    double x,y;
};

int N,K,st[120100]; point a[120100];

double area(point A, point B, point C)
{
    return (A.x*B.y+B.x*C.y+C.x*A.y-B.y*C.x-C.y*A.x-A.y*B.x);
}

inline bool cmp(point A, point B)
{
    return (area(a[1],A,B)>0);
}

int main(){
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    int i, ind=1;
    scanf("%d", &N);
    for (i=1; i<=N; i++)
    {
        scanf("%lf %lf",&a[i].x,&a[i].y);
        if (a[i].x<a[ind].x) ind=i;
    }

    swap(a[1],a[ind]);
    sort(a+2,a+N+1,cmp);
    a[N+1]=a[1];

    K=1,st[1]=1;
    for (i=2; i<=N; i++)
    {
        st[++K]=i;
        while (area(a[st[K-1]],a[st[K]],a[i+1])<0) K--;
    }


    printf("%d\n",K);
    for (i=1; i<=K; i++)
        printf("%.9lf %.9lf\n", a[st[i]].x, a[st[i]].y);

    return 0;
}