Cod sursa(job #1110988)

Utilizator TeOOOVoina Teodora TeOOO Data 18 februarie 2014 15:53:02
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
//Include
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

FILE *in, *out;

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

//Definitii
#define point_t pair<double, double>
#define x second
#define y first

#define pb push_back
#define popb pop_back

#define leftTurn(a, b, c) (det(a, b, c)>0)

//Functii
double det(point_t a, point_t b, point_t c)
{   return (a.x*b.y + b.x*c.y + c.x*a.y - c.x*b.y - a.x*c.y - b.x*a.y); }

bool angle(point_t a, point_t b);

//Variabile
int num;
point_t minPoint;
point_t points[sz];
vector <point_t> answer;

//Main
int main()
{
	in = fopen("infasuratoare.in", "rt");
	out = fopen("infasuratoare.out", "wt");
    fscanf(in,"%d", &num);
    fscanf(in,"%lf%lf", &minPoint.x, &minPoint.y);

    for(int i=1; i<num; ++i)
    {
        fscanf(in,"%lf%lf", &points[i].x, &points[i].y);
        if(points[i] < minPoint)
            swap(points[i], minPoint);
    }

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

    answer.reserve(num);
    answer.pb(minPoint);
    answer.pb(points[1]);

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

    fprintf(out, "%d\n", answer.size());
    vector<point_t>::iterator it, end= answer.end();
    for(it=answer.begin(); it!=end; ++it)
        fprintf(out,"%lf %lf\n", it->x, it->y);


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

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