Cod sursa(job #723253)

Utilizator horeste12Stoianovici Horatiu Andrei horeste12 Data 25 martie 2012 10:34:36
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include<fstream>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

struct punct
{
   double x,y;
} p[120010];

int n,pi/*punct initial*/;
int s[120010];
int st[120010],vf,cur;
void citire()
{
    f>>n;
    for(int i=1;i<=n;i++)
        f>>p[i].x>>p[i].y;
    f.close();
}
int comp(int a,int b)
{
   return (double)(p[a].x-p[pi].x)*(p[b].y-p[pi].y)<(double)(p[b].x-p[pi].x)*(p[a].y-p[pi].y);
}

long double semn(int x1, int x2, int x3)
{
    return (long double)p[x1].x*p[x2].y+p[x2].x*p[x3].y+p[x3].x*p[x1].y-p[x3].x*p[x2].y-p[x1].x*p[x3].y-p[x2].x*p[x1].y;
}
int main()
{
    citire();
    p[0].x=p[0].y=inf;
    for(int i=1;i<=n;i++)
        if(p[i].x<p[pi].x)
            pi=i;
    for(int i=1;i<=n;i++)
        if(i!=pi)
            s[++s[0]]=i;
    sort(s+1,s+s[0]+1,comp);
    st[1]=pi;st[2]=s[1];vf=2;
    for(int i=2;i<=s[0];i++)
    {
        cur=s[i];
        while(semn(st[vf],st[vf-1],cur)<0&&vf>1)
        {
            st[vf--]=0;
        }
        st[++vf]=cur;
    }
    while(semn(st[vf],st[vf-1],st[1])<0)
    {
        st[vf--]=0;
    }
    g<<vf<<'\n';
    for(int i=vf;i>0;i--)
        g<<p[st[i]].x<<' '<<p[st[i]].y<<'\n';
    return 0;
}