Cod sursa(job #1609646)

Utilizator PaulCbnCiobanu Paul PaulCbn Data 22 februarie 2016 22:03:07
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <limits.h>
#include <stack>

#define MAX 1000000000
using namespace std;

struct Point
{
    float x, y;
} O,v[120100],stiva[120100],prev;

int N,H,head;


bool compare(Point p1, Point p2)
{
    float a = (p1.x - O.x) * (p2.y - O.y);
    float b = (p2.x - O.x) * (p1.y - O.y);
    return a >= b;
}

bool spre_dreapta(Point p0,Point p1, Point p2)
{
    float u1,u2,v1,v2;
    u1 = p1.x - p0.x;
    u2 = p1.y - p0.y;

    v1 = p2.x - p0.x;
    v2 = p2.y - p0.y;

    return (u1*v2 - u2*v1) < 0;
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&N);
    O.x = MAX;
    O.y = MAX;
    int pos;
    for(int i=1; i<=N; ++i)
    {
        scanf("%f%f",&v[i].x,&v[i].y);
        if(O.x > v[i].x || O.x == v[i].x && O.y > v[i].y)
        {
            O = v[i];
            pos = i;
        }
    }
    swap(v[1], v[pos]);
    sort(v+2,v+N+1,compare);

    stiva[1]=v[1];
    stiva[2]=v[2];
    head = 2;
    for(int i=3; i<=N; i++)
    {
            while(head>=2&&spre_dreapta(stiva[head-1],stiva[head],v[i]))
                    head--;
            stiva[++head]= v[i];
    }

    printf("%d\n",head);

    for(int i=1;i<=head;i++)
        printf("%f %f\n",stiva[i].x,stiva[i].y);


    return 0;
}