Cod sursa(job #2019673)

Utilizator Stoica_StefanStoica Stefan Stoica_Stefan Data 8 septembrie 2017 12:11:07
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.87 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);
}

bool equal(double a, double b)
{
    return fabs(a - b) < EPS;
}

double crossProduct(point p1, point p2, point p3)
{
    return (p2.x - p1.x) * (p3.y - p2.y) - (p2.y - p1.y) * (p3.x - p2.x);
}

int ccw(point p1, point p2, point p3)
{
   double cp = crossProduct(p1, p2, p3);
   if(equal(cp, 0.0))
        return 0;
   if(cp < 0) return -1;
   return 1;
}

bool cmp(point p1, point p2)
{
    double cw = ccw(LL, p1, p2);
    if(cw == 1) return 1;
    else if(cw == -1)   return 0;
    else
    {
        if(dist(LL, p1) < dist(LL, p2)) return 1;
        else return 0;
    }
}

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