Cod sursa(job #673024)

Utilizator nutipasa16Macovei Claudiu nutipasa16 Data 3 februarie 2012 18:36:35
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.29 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
#define eps 1e-12
#define max_n 120001
int n,i,h;
typedef struct punct {double x,y;};
punct p[max_n],v[max_n];
int s[max_n],ok[max_n];
inline int cmp1(double a,double b) 
	{if (a+eps<b) return 1;
	 if (b+eps<a) return -1;
	 return 0;
	}

bool cmp(const punct &a,const punct &b) /* functia de comparare a coordonatelor punctelor: cresator dupa x si, in caz de egalitate, crescator dupa y*/
	{int t;
	 t=cmp1(a.x,b.x);
	 if (t!=0) return t==1;
	 return (cmp1(a.y,b.y)==1);
	}

int semn(punct a,punct b,punct c) /* se verifica daca punctul C(care este testat) se afla de o parte sau alta a dreptei AB utilizandu-se formula cu determinanti a ariei triunghiului ABC */
	{double A,B,C;
	 A = a.y-b.y;
	 B = b.x-a.x;
	 C = a.x*b.y - b.x*a.y;
	 return cmp1(A*c.x+B*c.y+C,0);
	 }

void rezolva() 
	{int k,q;
	 sort(v+1,v+n+1,cmp); //se sorteaza punctele dupa x, iar in caz de egalitate, dupa y
	 s[1]=1; s[2]=2; /* se initializeaza stiva S, in care se introduce cel mai din stanga punct, care se va afla sigur pe infasuratoare, si cel de-al 2-lea punct, care urmeaza sa fie verificat */
	 ok[2]=1; // vectorul de ok[], va contoriza introducerea sau scoaterea unui punct din stiva
	 k=2; // k=nr de elemente din stiva
	 i=3; // i=indicele punctului care urmeaza sa fie verificat pentru a stabili daca se afla pe infasuratoare
	 q=1; /*q=1 -> incrementarea indicelui punctului; q=-1 -> decrementarea indicelui punctului cand se ajunge la cel mai din dreapta punct (i==n) */
	while (!ok[1]) // nu s-a inchis poligonul convex
		{while (ok[i]) // se cauta un punct neutilizat inca pe infasuratoare
			{if (i==n) q=-1;
			 i+=q;
			}
		while (k>=2 && semn(v[s[k-1]],v[s[k]],v[i])==-1) //verificare daca punctul respecta proprietatea prin functia "semn"
			{ok[s[k--]]=0; //scoatere din stiva
			}
		s[++k]=i; //introducerea punctului valid in stiva
		ok[i]=1;
		}
	h=k-1; // h=nr de puncte de pe infasuratoare
	}

int main () 
	{freopen("infasuratoare.in","r",stdin);
	 freopen("infasuratoare.out","w",stdout);
	 scanf("%d",&n);
	 for (i=1; i<=n; i++)
	 scanf("%lf%lf",&v[i].x,&v[i].y);
	 rezolva();
	 printf("%d\n",h);
	 for (i=2; i<=h+1; i++)
	 printf("%lf %lf\n",v[s[i]].x,v[s[i]].y); // punctele de pe infasuratoare
	 return 0;
	}