Cod sursa(job #1472477)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 17 august 2015 09:23:30
Problema Infasuratoare convexa Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.13 kb
#include<stdio.h>
#include<stdlib.h>
struct P { double x,y; };
int n,i,g,w,u,v,j,t,l;
P d[120001],c[120001],e[120001],b[120001];
double k;
int A(const void *a,const void *b) {
    P *c=(P*)a,*d=(P*)b;
    return c->x<d->x||(c->x==d->x&&c->y<d->y);
}
double S(P a,P b,P p) { return (b.x-a.x)*(p.y-a.y)-(p.x-a.x)*(b.y-a.y); }
int main() {
	freopen("infasuratoare.in","r",stdin),freopen("infasuratoare.out","w",stdout),scanf("%d",&n);
	for(i=1;i<=n;i++)
    	scanf("%lf%lf",&d[i].x,&d[i].y);
	qsort(d,n,sizeof(d),A),v=u=g=1,w=n,c[1]=e[1]=d[g];
	for(i=2;i<n;i++) {
		k=S(d[g],d[w],d[i]);
      	if(k<0)
      		for(c[++u]=d[i];u>2&&S(c[u-2],c[u],c[u-1])>0;c[u-1]=c[u--]);
      	else if(k>0)
            for(e[++v]=d[i];v>2&&S(e[v-2],e[v],e[v-1])<0;e[v-1]=e[v--]);
	}
	for(e[++v]=c[++u]=d[w],t=v,l=u;t>2;)
    if(S(e[t-2],e[t],e[t-1])<0)
        e[t-1]=e[v--];
    else
        t--;
	for(;l>2;)
    if(S(c[l-2],c[l],c[l-1])>0)
        c[l-1]=c[u--];
    else
        l--;
	printf("%d\n",v+u-2);
	for(i=1;i<=u;i++)
      	printf("%lf %lf\n",c[i].x,c[i].y);
	for(j=v-1;j>1;j--)
      	printf("%lf %lf\n",e[j].x,e[j].y);
}