Cod sursa(job #1603353)

Utilizator andru47Stefanescu Andru andru47 Data 17 februarie 2016 13:55:21
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <bits/stdc++.h>
#define point pair<double,double>
#define x first
#define y second
#define eps 10e-12
using namespace std;
const int NMAX = 120000 + 5;
point a[NMAX];
int n,s[NMAX];
bool ok[NMAX];
int comp(double X,double Y)
{
    if (X+eps<Y)return 1;
    else if (Y+eps<X)return 2;
    return 0;
}
bool cmp(point X,point Y)
{
    int mare = comp(X.x,Y.x);
    if (mare==2)return false;
    else if (mare==1)return true;
    mare = comp(X.y,Y.y);
    if (mare==2)return false;
    return true;
}
int determinant(point a,point b,point c)
{
    int A,B,C;
    A=a.y-b.y;
    B=b.x-a.x;
    C=a.x*b.y-a.y*b.x;
    return (comp(A*c.x+B*c.y+C,0));
}
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d", &n);
    for (int i = 1; i<=n; ++i)
        scanf("%lf %lf\n", &a[i].x, &a[i].y);
    sort(a+1,a+n+1,cmp);
    ok[2]=true;
    int nr = 2;
    int nextt = 3;
    int icre = 1;
    s[1]=1;
    s[2]=2;
    while(ok[1]==false)
    {
        while(ok[nextt]==true)
        {
            if (nextt==n)icre = -1;
            nextt += icre;
        }
        while(nr>=2&&determinant(a[s[nr-1]],a[s[nr]],a[nextt])==2)
            ok[s[nr--]]=false;
        ok[nextt]=true;
        s[++nr]=nextt;
    }
    int puncte = nr-1;
    printf("%d\n", puncte);
    for (int i = 2; i<=puncte+1; ++i)
        printf("%lf %lf\n",a[s[i]].x,a[s[i]].y);
    return 0;
}