Cod sursa(job #895531)

Utilizator andreas_mihAndreas Mihaloianis andreas_mih Data 27 februarie 2013 11:42:21
Problema Infasuratoare convexa Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
#include<stack>
#define mp make_pair
#define x first
#define y second
using namespace std;
FILE*in=fopen("infasuratoare.in","r");
FILE*out=fopen("infasuratoare.out","w");
int nr;
vector <pair<double,double> > stiva;
pair<double,double> minim;
int determinant(double x1,double x2,double y1,double y2,double z1,double z2)
{
    return(x1*y2+x2*z1+y1*z2-x2*y1-y2*z1-z2*x1);
};
bool comparare(pair<double,double> a,pair<double,double> b)
{
    if(determinant(minim.x,minim.y,a.x,a.y,b.x,b.y)>0)
        return true;
    else
        return false;
};
pair<double,double> v[120001];
int main()
{
    fscanf(in,"%d",&nr);
    fscanf(in,"%lf%lf",&minim.x,&minim.y);
    for(int i=1;i<nr;++i)
    {
        double data1,data2;
        fscanf(in,"%lf%lf",&data1,&data2);
        if(data2<=minim.y && data1<minim.x)
        {
            pair<double,double> aj;
            aj=minim;
            minim.x=data1;
            minim.y=data2;
            data1=aj.x;
            data2=aj.y;
        }
        v[i]=mp(data1,data2);
    }
    sort(v+1,v+nr,comparare);
    stiva.push_back(minim);
    stiva.push_back(v[1]);
    for(int i=2;i<nr;++i)
    {
        while(0.0>determinant(stiva[stiva.size()-2].x,stiva[stiva.size()-2].y,stiva[stiva.size()-1].x,stiva[stiva.size()-1].y,v[i].x,v[i].y))
            stiva.pop_back();
        stiva.push_back(v[i]);
    }
    fprintf(out,"%d\n",stiva.size());
    for(int i=0;i<stiva.size();++i)
        fprintf(out,"%lf %lf\n",stiva[i].x,stiva[i].y);
fclose(in);
fclose(out);
return 0;
}