Cod sursa(job #1603675)

Utilizator aokirisakiLisca Ana aokirisaki Data 17 februarie 2016 18:35:30
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cmath>

const double eps=1.e-14;

struct point {double x,y;};

point P[120005],LL;

int n;

double dist(point P1,point P2)
{
	return (P1.x-P2.x)*(P1.x-P2.x)+(P1.y-P2.y)*(P1.y-P2.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);
}
int ccw(point P1,point P2,point P3)
{
	double ccp;
	ccp=cp(P1,P2,P3);
	
	if(fabs(ccp<eps))
		return 0;
	if(ccp>=eps)
		return 1;
	return -1;
}

bool cmp(point P1, point P2)
{
	double d1,d2;
	int cccw;
	
	cccw=ccw(LL,P1,P2);
	
	d1=dist(LL,P1);
	d2=dist(LL,P2);
	
	if(cccw==0)
	{
		if(d1<d2)
			return 1;
		else return 0;
	}
	else if(cccw==1)
		return 1;
	else return 0;
}

using namespace std;

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    
    double a,b;
    
    int i;
    
    scanf("%d",&n);
    
    scanf("%lf%lf",&a,&b);
    P[1].x=a;
    P[1].y=b;
    
    for(i=2;i<=n;i++)
	{
		scanf("%lf%lf",&a,&b);
		P[i].x=a;
		P[i].y=b;
		
		if(P[i].y-P[1].y<=-eps)
			swap(P[i],P[1]);
		
		else if(fabs(P[i].y-P[1].y)<eps && (P[i].x-P[1].x)<=-eps)
             swap(P[i],P[1]);

	}
	
	LL=P[1];
	
	sort(P+2,P+n+1,cmp);
	
	P[n+1]=P[1];
	
	int top=1,st[120005];
	
	st[top]=1;
	
	top++;
	
	st[top]=2;
	
	i=3;
	
	while(i<=n+1)
	{
		if(ccw(P[st[top-1]],P[st[top]],P[i])>0)
		{
			st[++top]=i;
			i++;
		}
		
		else top--;
	}
	
	top--;
	
	printf("%d\n",top);
	
	for(i=1;i<=top;i++)
		printf("%lf %lf\n",P[st[i]].x,P[st[i]].y);
    
    return 0;
}