Cod sursa(job #1878033)

Utilizator mateigabriel99Matei Gabriel mateigabriel99 Data 13 februarie 2017 20:48:22
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 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 cmp(Point a,Point b)
{
    return cross_product(point[1],a,b)<0;
}

int main()
{
    fin>>N;
    for(int i=1;i<=N;i++)
    {
        double a,b;
        fin>>a>>b;
        point[i].x=a; point[i].y=b;
    }
    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,cmp);
    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;
}