Cod sursa(job #902312)

Utilizator TeOOOVoina Teodora TeOOO Data 1 martie 2013 13:37:30
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

//Definitii
#define point pair<double, double>
#define leftTurn(a,b,c) (det(a,b,c)>0)

//Constante
const int sz = (int)12e4+1;

//Functii
double det(point a, point b, point c)
{   return a.first*b.second + b.first*c.second + c.first*a.second - b.second*c.first - c.second*a.first - b.first*a.second;    }

//Variabile
FILE *in,*out;

int num;
point points[sz];
point minPoint, current;
vector<point> convexeShell;

bool angle(point a, point b)
{   return leftTurn(minPoint,a,b); }

int main()
{
    in=fopen("infasuratoare.in","rt");
    out=fopen("infasuratoare.out","wt");
    fscanf(in,"%d", &num);
    fscanf(in,"%lf%lf",&minPoint.first,&minPoint.second);

    for(int i=1; i<num; ++i)
    {
        fscanf(in,"%lf%lf",&current.first,&current.second);
        if(current.second < minPoint.second  || current.second == minPoint.second && current.first < minPoint.first)
        {
            points[i] = minPoint;
            minPoint = current;
        }
        else points[i] = current;
    }


    //for(int i=1; i<=num; ++i)
     //   fprintf(out,"%lf %lf\n", points[i].first, points[i].second);

    sort(points+1, points+num, angle);

    convexeShell.reserve(num);
    convexeShell.push_back(minPoint);
    convexeShell.push_back(points[1]);

    for(int i=2; i<num; ++i)
    {
        while(!leftTurn(convexeShell.at(convexeShell.size()-2), convexeShell.at(convexeShell.size()-1), points[i]))
            convexeShell.pop_back();
        convexeShell.push_back(points[i]);
    }

    fprintf(out,"%d\n",convexeShell.size());
    vector<point>::iterator it, end = convexeShell.end();
    for(it=convexeShell.begin(); it!=end; ++it)
        fprintf(out,"%lf %lf\n", it->first, it->second);


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