Cod sursa(job #964640)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 21 iunie 2013 19:57:49
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include<algorithm>
#include<stack>
#include<cstdio>
using namespace std;
struct pct {double x,y;} a[120001],st[120001];
int n,vf=-1;

struct cmp{
            bool operator ()(const pct p1,const pct p2)const
            {
                if(p1.x<p2.x)return 1;
                if(p1.x==p2.x&&p1.y<p2.y)return 1;
                return 0;
            }
          };

int parte(pct a,pct b,pct m)
{
    return a.x*b.y+b.x*m.y+m.x*a.y-m.y*a.x-a.y*b.x-m.x*b.y;
}

int main()
{
    FILE *f=fopen("infasuratoare.in","r");
    int i;
    fscanf(f,"%d",&n);
    for(i=0;i<n;i++)
        fscanf(f,"%lf%lf",&a[i].x,&a[i].y);
    sort(a,a+n,cmp());
    st[++vf]=a[0];
    i=1;
    while(i+1<n && parte(a[0],a[n-1],a[i])<0)i++;
    if(i+1<n)st[++vf]=a[i];
    i++;
    while(i+1<n)
        if(parte(a[0],a[n-1],a[i])>0)//deci a[i] e din jumatatea de sus
        {
            st[++vf]=a[i];
            if(parte(st[vf-2],st[vf],st[vf-1])>0)i++;
                else
                    if(vf>1)vf-=2;
        }
        else i++;
    st[++vf]=a[n-1];
    i=n-2;
    while(i>0)
        if(parte(a[0],a[n-1],a[i])<0)
        {
            st[++vf]=a[i];
            if(parte(st[vf-2],st[vf],st[vf-1])>0)i--;
                            else
                    if(vf>1)vf-=2;
        }
        else i--;
    f=fopen("infasuratoare.out","w");
    fprintf(f,"%d\n",vf+1);
    while(vf+1)
    {
        fprintf(f,"%lf %lf\n",st[vf].x,st[vf].y);
        vf--;
    }
    return 0;
}