Cod sursa(job #1605706)

Utilizator IulianBogIulian Bogdanovici IulianBog Data 19 februarie 2016 13:38:09
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
const double eps=1.e-12;
using namespace std;
struct point
{
	double x,y;
}
int p[120005],ll;
double dist(point p1, point p2)
{
	return (p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y);
}
double cp(point p1, point p2, point p3)
{
	return (p2.x-p1.x)*(p3.y-p2.y)-(p2.y-p1.y)*(p3.x-p2.x);
}
inline int ccw(point p1, point p2, point p3)
{
	double ccc=cp(p1,p2,p3);
	if(fabs(ccc)<eps)
		return 0;
	if(ccc<=-eps)
		return -1;
	return 1;
}
bool cmp(point p1, point p2)
{
	double d1,d2;int ccv=ccw(ll,p1,p2);
	d1=dist(ll,p1);
	d2=dist(ll,p2);
	if(ccv==-1)
		return 0;
	if(ccv==1)
		return 1;
	if(d1<d2)
		return 1;
	return 0;
}
int v[120005];
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int n;
    register int i;
    scanf("%d",&n);
    double x,y;
    scanf("%lf",&x,&y);
    for(i=2;i<=n;++i)
    {
    	scanf("%lf%lf",&p[i].x,&p[i].y);
    	if(p[i].y-p[1].y<=-eps)
			swap(p[i],p[1]);
		if(fabs(p[i].y-p[1].y)<eps)
			if(p[i].x-p[1].x<=-eps)
				swap(p[i],p[1]);
    }
    ll.x=p[1].x;
    ll.y=p[1].y;
    sort(p+2,p+n+1,cmp);
	p[n+1]=ll;
	v[1]=1;
	v[2]=2;
	int top;
	while(i<=n+1)
	{
		if(ccw(p[v[top-1]],p[v[top-2]],p[i])!=-1)
		{
			v[++top]=i;
			++i;
		}
		else
			top--;
	}
	top--;
	printf("%d",top);
	for(i=1;i<=top;++i)
	{
		printf("%lf %lf\n",p[v[i]].x,p[v[i]].y);
	}
    return 0;
}