Cod sursa(job #871117)

Utilizator andreas_mihAndreas Mihaloianis andreas_mih Data 4 februarie 2013 14:46:01
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include<stdio.h> // Visane, ce zici de asta ?
#include<vector>  // [email protected]
#include<math.h>
#include<algorithm>
using namespace std;
FILE*in=fopen("infasuratoare.in","r");
FILE*out=fopen("infasuratoare.out","w");
vector <pair<double,double> >stiva;
pair<double,double> v[120001],minim;
int nr_puncte;
double determinant(double A,double a,double B,double b,double C,double c)
{
  return(C*a + c*B + A*b - a*B - b*C - c*A);
};
bool angle(pair<double,double> a,pair<double,double> b)
{
   if(determinant(minim.first,minim.second,a.first,a.second,b.first,b.second)>0)
        return true;
    else
        return false;
};
int main()
{
    fscanf(in,"%d",&nr_puncte);
    fscanf(in,"%lf%lf",&minim.first,&minim.second);
    for(int i=1;i<nr_puncte;++i)
    {
        double punctA,punctB;
        fscanf(in,"%lf%lf",&punctA,&punctB);
        if(make_pair(punctB, punctA) < make_pair(minim.second, minim.first))
        {
            v[i] = minim;
            minim = make_pair(punctA,punctB);//
        }
        else
            v[i]=make_pair(punctA,punctB);
    }
    sort(v+1,v+nr_puncte,angle);
    stiva.push_back(minim);
    stiva.push_back(v[1]);
    for(int i=2;i<nr_puncte;++i)
        {
            while(0.0>determinant(stiva[stiva.size()-2].first,stiva[stiva.size()-2].second,stiva[stiva.size()-1].first,stiva[stiva.size()-1].second,v[i].first,v[i].second))
                stiva.pop_back();
            stiva.push_back(v[i]);
        }
        fprintf(out,"%d\n",(int)stiva.size());
    for(int i=0;i<(int)stiva.size();++i)
        fprintf(out,"%lf %lf\n",stiva[i].first,stiva[i].second);
fclose(in);
fclose(out);
}