Cod sursa(job #293262)

Utilizator ScrazyRobert Szasz Scrazy Data 1 aprilie 2009 09:44:07
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

const int maxn = 121000;
#define eps 1e-9
struct point
{
    double x, y; 
    point(){} 
    point(double nx, double ny){x = nx; y = ny;} 
};

int n; 
vector<point> v1, v;
vector<point> S;

point first;

int cmp(point a, point b)
{ 
    return (double)(a.x - first.x) * (b.y - first.y) > (double)(a.y - first.y) * (b.x - first.x);
}

double trig(point a, point b, point c)
{
    return (double)(b.x - a.x)*(c.y - a.y) - (double)(b.y - a.y)*(c.x - a.x); 
}

void read()
{
    scanf("%d", &n); 
    first.x = 1e9; first.y = 1e9;
    for (int i = 1; i <= n; ++i)
    {
	double x, y;
	scanf("%lf%lf", &x, &y);
	v1.push_back(point(x,y));
	if (x < first.x || (x == first.x && y < first.y))
	    first = point(x,y);
    }
    for (int i = 0; i < n; ++i) if (first.x != v1[i].x || first.y != v1[i].y) v.push_back(v1[i]);;
    sort(v.begin(), v.end(), cmp);
    //for (int i = 0; i < n - 1; ++i) fprintf(stderr,"%lf %lf\n", v[i].x, v[i].y);
}

void print()
{
    for (int i = 0; i < S.size(); ++i) fprintf(stderr,"%lf %lf\n", S[i].x, S[i].y);
    fprintf(stderr,"\n");
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);

    read(); 
    S.push_back(first);
    for (int i = 0; i < n - 1; ++i)
    {
	double t = 0;
	while(S.size() > 2 && (t = trig(S[S.size()-2],S[S.size()-1],v[i])) < 0) 
	{
	    //fprintf(stderr,"%lf-> %lf %lf - %lf %lf\n", t, S[S.size() - 1].x, S[S.size() - 1].y, S[S.size() - 2].x, S[S.size() - 2].y);
	    S.pop_back();
	}
	S.push_back(v[i]);
	//print();
    }
    S.push_back(first);
    printf("%d\n", S.size() - 1);
    for (int i = 1; i < S.size(); ++i)
	printf("%lf %lf\n", S[i].x, S[i].y);

    return 0;
}