Cod sursa(job #1226617)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 6 septembrie 2014 15:10:45
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
// GRAHAM SCAN O(nlogn)
using namespace std;
const double eps=1.e-12;
const int LIMIT=120005;
struct POINT
{
    double x,y;
}P[LIMIT];
inline bool ccw(const POINT &a, const POINT &b, const POINT &c)
{
    return (b.x-a.x)*(c.y-b.y)-(b.y-a.y)*(c.x-b.x)>0;
}
inline bool cmp(const POINT &a, const POINT &b)
{
    return ccw(P[0],a,b);
}
int st[LIMIT];
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int n,i,top;
    scanf("%d %lf %lf",&n,&P[0].x,&P[0].y); // P[0] = low left
    for(i=1;i<n;++i)
    {
        scanf("%lf %lf",&P[i].x,&P[i].y);
        if((fabs(P[i].y-P[0].y)<eps && P[i].x-P[0].x<=-eps) || P[i].y-P[0].y<=-eps)
            swap(P[0],P[i]);
    }
    sort(P+1,P+n,cmp);
    P[n]=P[0];
    st[0]=0;
    st[1]=1;
    top=1;
    i=2;
    while(i<=n)
    {
        if(ccw(P[st[top-1]],P[st[top]],P[i]))
            st[++top]=i++;
        else
            --top;
    }
    printf("%d\n",top);
    for(i=0;i<top;++i)
        printf("%6lf %6lf\n",P[st[i]].x,P[st[i]].y);
    fclose(stdin);
    fclose(stdout);
    return 0;
}