Cod sursa(job #2176028)

Utilizator VladG26Ene Vlad-Mihai VladG26 Data 16 martie 2018 20:29:23
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
struct punct
{
    double x,y;
    bool trigorder(punct p1,punct p2)
    {
        double r=(p1.x*p2.y+x*p1.y+y*p2.x-p1.x*y-p2.x*p1.y-p2.y*x);
        return (p1.x*p2.y+x*p1.y+y*p2.x-p1.x*y-p2.x*p1.y-p2.y*x)>0;
    }
}vPuncte[120005];
int n;
void citire()
{
    scanf("%d",&n);
    int idx=1;
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf",&vPuncte[i].x,&vPuncte[i].y);
        if((vPuncte[i].x<vPuncte[idx].x)||(vPuncte[i].x==vPuncte[idx].x&&vPuncte[i].y<vPuncte[idx].y))
        {
            idx=i;
        }
    }
    swap(vPuncte[1],vPuncte[idx]);
}
bool cmp(punct p1,punct p2)
{
    return vPuncte[1].trigorder(p1,p2);
}
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    citire();
    sort(vPuncte+2,vPuncte+n+1,cmp);
    int stiva[120005],idx=2;
    stiva[1]=1;
    stiva[2]=2;
    for(int i=3;i<=n;i++)
    {
        if(vPuncte[stiva[idx-1]].trigorder(vPuncte[stiva[idx]],vPuncte[i])||idx<2)
        {
            stiva[++idx]=i;
        }
        else
        {
            idx--;
            i--;
        }
    }
    printf("%d\n",idx);
    for(int i=1;i<=idx;i++)
    {
        printf("%f %f\n",vPuncte[stiva[i]].x,vPuncte[stiva[i]].y);
    }
    return 0;
}