Cod sursa(job #1401962)

Utilizator IonSebastianIon Sebastian IonSebastian Data 26 martie 2015 11:22:29
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.33 kb
#include <cstdio>
#include <algorithm>
using namespace std;

FILE *in, *out;

const int MAX_N = 120000;
const int INF = 1000000000;

long double dist(double x1, double y1, double x2, double y2)
{
    return ((long double)(x1-x2)*(x1-x2) + (long double)(y1-y2)*(y1-y2));
}

struct point2Ddouble
{
    double x, y;
};

point2Ddouble points[MAX_N];
point2Ddouble p0;
point2Ddouble elements[MAX_N];

int nre;

void push(point2Ddouble e)
{
    elements[nre].x = e.x;
    elements[nre].y = e.y;
    nre++;
}

void pop()
{
    nre--;
}

point2Ddouble top()
{
    return elements[nre-1];
}

point2Ddouble nextToTop()
{
    return elements[nre-2];
}

void change(int a, int b)
{
    point2Ddouble aux;
    aux.x = points[a].x;
    aux.y = points[a].y;
    points[a].x = points[b].x;
    points[a].y = points[b].y;
    points[b].x = aux.x;
    points[b].y = aux.y;
}

long double ccw(point2Ddouble p1, point2Ddouble p2, point2Ddouble p3)
{
    return ((long double)p1.x*p2.y+(long double)p2.x*p3.y+(long double)p3.x*p1.y-(long double)p1.y*p2.x-(long double)p2.y*p3.x-(long double)p3.y*p1.x);
}

bool cmp(point2Ddouble a, point2Ddouble b)
{
    long double turn = ccw(p0,a,b);
    if(turn == 0)
    {
        return (dist(p0.x,p0.y,a.x,a.y) < dist(p0.x,p0.y,b.x,b.y));
    }
    return (turn > 0);
}

int main()
{
    in = fopen("infasuratoare.in", "r");
    out = fopen("infasuratoare.out", "w");
    int n, i;
    int lowestPointIndex;
    p0.y = INF;
    fscanf(in, "%d", &n);
    //in >> n;
    for(i = 0; i < n; i++)
    {
        fscanf(in, "%lf%lf", &points[i].x, &points[i].y);
        //in >> points[i].x >> points[i].y;
        if(points[i].y < p0.y)
        {
            p0.y = points[i].y;
            p0.x = points[i].x;
            lowestPointIndex = i;
        } else if(points[i].y == p0.y && points[i].x < p0.x)
        {
            p0.x = points[i].x;
            lowestPointIndex = i;
        }
    }
    change(0,lowestPointIndex);
    nre = 0;
    sort(points+1,points+n,cmp);
    push(points[0]);
    push(points[1]);
    for(i = 2; i < n; i++)
    {
        while(nre >= 2 && ccw(nextToTop(),top(),points[i]) <= 0)
        {
            pop();
        }
        push(points[i]);
    }
    fprintf(out, "%d\n", nre);
    for(i = 0; i < nre; i++)
    {
        fprintf(out, "%.6lf %.6lf\n", elements[i].x, elements[i].y);
    }
    fclose(in);
    fclose(out);
    return 0;
}