Cod sursa(job #902240)

Utilizator andreas_mihAndreas Mihaloianis andreas_mih Data 1 martie 2013 13:22:52
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
#define x first
#define y second
#define mp make_pair
using namespace std;
FILE*in=fopen("infasuratoare.in","r");
FILE*out=fopen("infasuratoare.out","w");
int n;
vector <pair<double,double> > q;
pair<double,double> minim;
double determinant(pair<double,double>a,pair<double,double>b,pair<double,double>c)
{
    return(a.x*b.y+b.x*c.y+a.y*c.x-a.y*b.x-b.y*c.x-c.y*a.x);
};
bool byAngle(pair<double,double> a, pair<double,double> b)
{
    if(determinant(minim,a,b)<0)
        return true;
    else
        return false;
};
pair<double,double> v[120001];
int main()
{
    fscanf(in,"%d",&n);
    double data1,data2;
    fscanf(in,"%lf%lf",&data1,&data2);
    minim=mp(data2,data1);
    for(int i=1;i<n;++i)
    {
        double data1,data2;
        fscanf(in,"%lf%lf",&data1,&data2);
        pair<double,double> actual=mp(data2,data1);
        if(minim > actual)
            swap(minim,actual);
        v[i]=mp(actual.x,actual.y);

    }
    sort(v+1,v+n,byAngle);
    q.push_back(minim);
    q.push_back(v[1]);
    for(int i=2;i<n;++i)
    {
        while(0.0<determinant(q[q.size()-2],q[q.size()-1],v[i]))
            q.pop_back();
        q.push_back(v[i]);
    }
    fprintf(out,"%d\n",(int)q.size());
    for(int i=0;i<(int)q.size();++i)
        fprintf(out,"%lf %lf\n",q[i].y,q[i].x);

fclose(in);
fclose(out);
return 0;
}