Cod sursa(job #2173662)

Utilizator maria_sinteaMaria Sintea maria_sintea Data 15 martie 2018 23:24:37
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstdio>
#define N 120005
#define inf 0x3f3f3f3f

using namespace std;

struct punct
{
    double x, y, unghi;
}a[N], s[N];
int n, ns;
double xmin=inf, ymin=inf;

int cmp(punct e, punct f)
{
    return (e.unghi<f.unghi);
}

int cmp2(punct e, punct f)
{
    e.unghi=atan2(e.y, e.x);
    f.unghi=atan2(f.y, f.x);
    return (e.unghi<=f.unghi);
}

void citire()
{
    scanf("%d\n", &n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lf %lf\n", &a[i].x, &a[i].y);
        a[i].unghi=0;
        if(a[i].x<xmin)
            xmin=a[i].x, ymin=a[i].y;
        else
            if(a[i].x==xmin && a[i].y<ymin)
                ymin=a[i].y;
    }
}

void sortare_unghiuri()
{
    for(int i=1;i<=n;i++)
        if(xmin==a[i].x && ymin==a[i].y)
            a[i].unghi=-10;
        else
            a[i].unghi=atan2(a[i].y-ymin, a[i].x-xmin);
    sort(a+1, a+n+1, cmp);
}

double det(punct a, punct b, punct c)
{
    return a.x*b.y+b.x*c.y+a.y*c.x-b.y*c.x-c.y*a.x-b.x*a.y;
}

void solutie()
{
    s[++ns]=a[1];
    s[++ns]=a[2];
    for(int i=3;i<=n;i++)
    {
        punct p1=a[i], p2=s[ns], p3=s[ns-1];
        while(det(p1, p2, p3)>0 && ns>1)
        {
             ns--;
             p2=s[ns];
             p3=s[ns-1];
        }
        s[++ns]=p1;
    }
}

void afisare()
{
    printf("%d\n", ns);
    sort(s+1, s+ns+1, cmp2);
    for(int i=1;i<=ns;i++)
        printf("%lf %lf\n", s[i].x, s[i].y);
}

int main()
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);

    citire();
    sortare_unghiuri();
//    for(int i=1;i<=n;i++)
//        printf("%lf %lf\n", a[i].x, a[i].y);
    solutie();
    afisare();
    return 0;
}