Cod sursa(job #1343652)

Utilizator Alex_dudeDudescu Alexandru Alex_dude Data 15 februarie 2015 18:51:05
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#define nmax 1000
using namespace std;
FILE *f1=fopen("infasuratoare.in","r"),*f2=fopen("infasuratoare.out","w");
struct punct
{
    double x,y;
}p0;

vector <punct> plan;
punct inf[nmax];
int n,vf;

double produs(punct a,punct b,punct c)
{
    return ((c.y-a.y)*(b.x-a.x)-(b.y-a.y)*(c.x-a.x));
}
bool comp(punct a,punct b)
{
    return produs(p0,a,b)>0;
}
void push(punct a)
{
    vf++;
    inf[vf]=a;
}
void pop()
{
    vf--;
}
int main()
{
    fscanf(f1,"%d",&n);
    for(;n;n--)
    {
        punct b;
        fscanf(f1,"%lf%lf",&b.x,&b.y);
        plan.push_back(b);
    }

    p0.x=plan[0].x;
    p0.y=plan[0].y;

    int i,a=0;
    punct aux;

    for(i=0;i<plan.size();i++)
    if(plan[i].x<p0.x || plan[i].x==p0.x&&plan[i].y<p0.y)
    {
        p0.x=plan[i].x;
        p0.y=plan[i].y;
        a=i;
    }

    aux=plan[0];
    plan[0]=plan[a];
    plan[a]=aux;

    sort(plan.begin()+1,plan.end(),comp);

    push(plan[0]);
    push(plan[1]);

    double o=0;
    for(i=2;i<plan.size();i++)
    {
        o=produs(inf[vf-1],inf[vf],plan[i]);
        if(o==0)
        {
            pop();
            push(plan[i]);
        }
        else if(o>0)push(plan[i]);
        else
        {
            while(o<=0 && vf>1)
            {
                pop();
                o=produs(inf[vf-1],inf[vf],plan[i]);
            }
            push(plan[i]);
        }
    }
    fprintf(f2,"%d\n",vf);
    for(i=1;i<=vf;i++)
    fprintf(f2,"%0.6f %0.6f\n",inf[i].x,inf[i].y);
    fclose(f1);
    fclose(f2);
    return 0;
}

//Our greatest weakness lies in giving up. The most certain way to succeed is always to try just one more time.