Cod sursa(job #1915122)

Utilizator mateigabriel99Matei Gabriel mateigabriel99 Data 8 martie 2017 19:47:10
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>

#define NMax 120005

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

int N,Top;
struct Point { double x,y; } point[NMax],Stack[NMax];

double cross_product(Point a, Point b, Point c)
{
    return a.x*b.y+a.y*c.x+b.x*c.y-c.x*b.y-b.x*a.y-a.x*c.y;
}

bool sortComp(Point a,Point b)
{
    return cross_product(point[1],a,b)<0;
}

int main()
{
    fin>>N;
    for(int i=1;i<=N;i++)
        fin>>point[i].x>>point[i].y;

    int pos=1;
    for(int i=2;i<=N;i++)
        if(point[i].x<point[pos].x)
            pos=i;

    swap(point[1],point[pos]);
    sort(point+2,point+N+1,sortComp);

    Stack[++Top]=point[1];
    Stack[++Top]=point[2];
    for(int i=3;i<=N;i++)
    {
        while(Top>=2 && cross_product(Stack[Top-1],Stack[Top],point[i])>0)
            Top--;
        Stack[++Top]=point[i];
    }

    fout<<Top<<"\n";
    for(int i=Top;i>0;i--)
        fout<<fixed<<setprecision(6)<<Stack[i].x<<" "<<Stack[i].y<<"\n";

    return 0;
}