Cod sursa(job #1645135)

Utilizator bleo16783FMI Bleotiu Cristian bleo16783 Data 10 martie 2016 11:12:15
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include<fstream>
#include<algorithm>
using namespace std;
int i,n,st[120001],vf,poz;
struct punct
{
    double x,y;
}p1,p2,p3,v[120001];

double intoarcere(punct a,punct b,punct c)
{
    double x=(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
    return x;
}
bool compare(punct a,punct b)
{
    return intoarcere(v[1],a,b)<0;
}
int main()
{
    ifstream f("infasuratoare.in");f>>n;
    for(i=1;i<=n;i++){f>>v[i].x>>v[i].y;}//cout<<v[i].x<<" "<<v[i].y<<'\n';}
    f.close();poz=1;
    for(i=2;i<=n;i++)
    {
        if(v[i].x==v[poz].x&&v[i].y<v[poz].y)poz=i;
        else if(v[i].x<v[poz].x)poz=i;
    }
    p1=v[poz];v[poz]=v[1];v[1]=p1;
    sort(v+2,v+1+n,compare);//for(i=1;i<=n;i++)cout<<v[i].x<<" "<<v[i].y<<'\n';
    st[1]=1;st[2]=2;vf=2;
    for(i=3;i<=n;i++)
    {
        while(vf>1&&intoarcere(v[st[vf-1]],v[st[vf]],v[i])>0)vf--;
        vf++;st[vf]=i;

    }
    ofstream g("infasuratoare.out");g<<vf<<'\n';
    for(i=vf;i>0;i--)
    {
        n=st[i];
        g<<v[n].x<<" "<<v[n].y<<'\n';
    }
    g.close();
    return 0;
}