Cod sursa(job #2110845)

Utilizator mirunafrancescaMiruna mirunafrancesca Data 21 ianuarie 2018 14:08:35
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <iostream>
#include <stdio.h>
#include <limits.h>
#include <algorithm>
using namespace std;

struct punct
{
    double x, y;
}a[120001];

punct p;

int det(punct a, punct b, punct c)
{
    int prod;

    prod=(a.x*b.y)+(c.x*a.y)+(b.x*c.y)-(c.x*b.y)-(c.y*a.x)-(b.x*a.y);

    return prod;
}

bool comp(punct A, punct B)
{
    return det(a[1],A,B)>=0;
}

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

    int n, poz=1, m=0;
    punct v[120001];

    cin>>n;
    for(int i=1; i<=n; i++)
    {
        scanf("%lf %lf \n", &a[i].x, &a[i].y);
        if((a[i].y<a[poz].y) || (a[i].y==a[poz].y && a[i].x<a[poz].x))
            poz=i;
    }

    swap(a[poz],a[1]);
    sort(a+2,a+n+1,comp);

    v[++m]=a[1];
    v[++m]=a[2];

    for(int i=3; i<=n; i++)
    {
        while(det(v[m-1],v[m],a[i])<=0)
        {
            m--;
        }
        v[++m]=a[i];
    }

    printf("%d \n", m);
    for(int i=1; i<=m; i++)
        printf("%.12lf %.12lf \n", v[i].x, v[i].y);


    return 0;
}