Cod sursa(job #2110549)

Utilizator vancea.catalincatalin vancea.catalin Data 20 ianuarie 2018 20:49:11
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#include<stack>
#include<iomanip>
 
#define INF 1100000000
#define DN 120100
using namespace std;
fstream fin("infasuratoare.in",ios::in),fout("infasuratoare.out",ios::out);
struct puncte
{
    double x,y;
} v[DN];
 
int n,ind,ap[DN],lst;
double xm=INF,ym=INF;
puncte st[DN];
 
bool cmp(puncte a,puncte b)
{
    if(a.x<b.x) return 1;
    if(a.x==b.x && a.y>b.y) return 1;
    return 0;
}
 
int det(puncte a,puncte b,puncte c)
{
    double xx=0;
    xx=a.x*b.y+b.x*c.y+a.y*c.x;
    xx=xx-c.x*b.y-a.y*b.x-a.x*c.y;
    if(xx>0) return 1;
    if(xx<0) return -1;
    return 0;
}
 
int main()
{
    int i,k;
    double x,y;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>x>>y;
        v[i]={x,y};
    }
    sort(v+1,v+n+1,cmp);
    st[1]=v[1];
    lst=1;
    for(i=2;i<=n;i++)
    {
        while(lst>1 && det(st[lst-1],st[lst],v[i]) > 0)
        {
            lst--;
        }
        lst++;
        st[lst]=v[i];
    }
    k=lst;
    for(i=n-1;i>=1;i--)
    {
        while(lst>k && det(st[lst-1],st[lst],v[i]) > 0)
        {
            lst--;
        }
        lst++;
        st[lst]=v[i];
    }
    lst--;
    fout<<lst<<"\n";
    for(i=lst;i>0;i--) fout<<fixed<<setprecision(12)<<st[i].x<<" "<<st[i].y<<"\n";
     
     
}