Cod sursa(job #1645072)

Utilizator bleo16783FMI Bleotiu Cristian bleo16783 Data 10 martie 2016 10:56:15
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include<fstream>
#include<algorithm>
using namespace std;
int i,n,st[120001],vf;
struct punct
{
    double x,y;
}p1,p2,p3,v[120001];
bool compare(punct a,punct b)
{
    if(a.y==b.y)return(a.x<b.x);
    return(a.y<b.y);
}
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;
}
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();
    sort(v+1,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=1;i<=vf;i++)
    {
        n=st[i];
        g<<v[n].x<<" "<<v[n].y<<'\n';
    }
    g.close();
    return 0;
}