Cod sursa(job #1730793)

Utilizator LucianTLucian Trepteanu LucianT Data 17 iulie 2016 16:54:31
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>
#define maxN 120005
#define f first
#define s second
using namespace std;
int n,i,j,top,poz=1;
pair<double,double> v[maxN],stk[maxN];
double det(pair<double,double>a,pair<double,double> b,pair<double,double>c)
{
    return (b.f-a.f)*(c.s-a.s)-(c.f-a.f)*(b.s-a.s);
}
bool cmp(pair<double,double> a,pair<double,double>b)
{
    return det(v[1],a,b)>0;
}
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%lf %lf",&v[i].f,&v[i].s);
        if(v[i]<v[poz])
            poz=i;
    }
    swap(v[poz],v[1]);
    sort(v+2,v+n+1,cmp);
    stk[++top]=v[1],stk[++top]=v[2];
    for(i=3;i<=n;i++)
    {
        while(top>=2 && det(stk[top-1],stk[top],v[i])<0)
            top--;
        stk[++top]=v[i];
    }
    printf("%d\n",top);
    for(i=1;i<=top;i++)
        printf("%.6lf %.6lf\n",stk[i].f,stk[i].s);
    return 0;
}