Cod sursa(job #2110822)

Utilizator mirunafrancescaMiruna mirunafrancesca Data 21 ianuarie 2018 13:37:34
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <iostream>
#include <stdio.h>
#include <limits.h>
#include <algorithm>
using namespace std;

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

punct p;

bool comp(punct a, punct b)
{
    return (a.y-p.y)/(a.x-p.x)<(b.y-p.y)/(b.x-p.x);
}

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;
}

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

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

    p.x=p.y=INT_MAX;

    cin>>n;
    for(int i=1; i<=n; i++)
    {
        scanf("%lf %lf \n", &a[i].x, &a[i].y);
        if((a[i].x<p.x) || (a[i].x==p.x && a[i].y<p.y))
        {
            p.x=a[i].x;
            p.y=a[i].y;
            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("%.6lf %.6lf \n", v[i].x, v[i].y);


    return 0;
}