Cod sursa(job #1883060)

Utilizator PaulCbnCiobanu Paul PaulCbn Data 17 februarie 2017 18:10:28
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#define NMAX 120005
using namespace std;

struct punct
{
    double x,y;
}puncte[NMAX],stiva[NMAX];
int N,K;


void citire()
{
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
    {
        scanf("%lf%lf",&puncte[i].x,&puncte[i].y);
        if(puncte[i].x<puncte[1].x)
            swap(puncte[1],puncte[i]);
        else if(puncte[i].x==puncte[1].x && puncte[i].y<puncte[1].y)
            swap(puncte[1],puncte[i]);
    }
}

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

bool comparare(punct p1,punct p2)
{
    return cross_prod(puncte[1],p1,p2)>0;
}

void rezolvare()
{
    sort(puncte+2,puncte+N+1    ,comparare);
    stiva[++K]=puncte[1];
    stiva[++K]=puncte[2];
    for(int i=3;i<=N;i++)
    {
        while(K>=2 && cross_prod(stiva[K-1],stiva[K],puncte[i])<0)
            K--;
        stiva[++K]=puncte[i];
    }
}

void afisare()
{
    for(int i=1;i<=K;i++)
        printf("%.6lf %.6lf\n",stiva[i].x,stiva[i].y);
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    citire();
    rezolvare();
    afisare();
    return 0;
}