Cod sursa(job #2019670)

Utilizator Stoica_StefanStoica Stefan Stoica_Stefan Data 8 septembrie 2017 12:07:12
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include <iostream>
#include <fstream>
#include <math.h>
#include <algorithm>
#include <cstdio>

using namespace std;

const double eps = 10e-12;

struct point
{
    double x, y;
};

point LL;

double dist(point a, point b)
{
    double dx = a.x-b.x, dy = a.y-b.y;
    return sqrt(dx*dx+dy*dy);
}

int ccw(point a, point b, point c)
{
    int cc = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
    if(cc == 0)  return 0;
    if(cc < 0)   return -1;
    if(cc > 0)   return 1;
}

int cmp(point A, point B)
{
    double d1, d2;
    int c = ccw(LL, A, B);
    if(c == 0)
    {
        d1 = dist(LL, A);
        d2 = dist(LL, B);
        if(d1 - d2 >= eps) return 0;
        return 1;
    }
    return c == 1;
}

ifstream fin("infasuratoare.in");

int main()
{
    freopen("infasuratoare.out", "w", stdout);
    int n;
    fin >> n;
    point p[n+2];
    for(int i = 1; i <= n; i++)
    {
        fin >> p[i].x >> p[i].y;
    }
    int ll = 1;
    for(int i = 2; i <= n; i++)
        if(p[i].y < p[ll].y || (p[i].y == p[ll].y && p[i].x < p[ll].x))
            ll = i;
    p[0] = p[ll];
    LL = p[ll];
    p[ll] = p[n];
    sort(p+1, p+n, cmp);
    p[n] = p[0];
    int h[n+1];
    h[0] = 0;
    h[1] = 1;
    int top = 1;
    int i = 2;
    while(i <= n)
    {
        if(ccw(p[h[top-1]], p[h[top]], p[i]) >= 0)
        {
            top++;
            h[top] = i;
            i++;
        }else top--;
    }
    i = n-1;
    while(ccw(LL, p[i-1], p[i]) == 0)
    {
        h[top++] = i-1;
        i--;
    }
    printf("%d\n", top);
    for(int i = 0; i < top; i++)
    {
        printf("%.6f %.6f\n", p[h[i]].x, p[h[i]].y);
    }
    return 0;
}