Cod sursa(job #844010)

Utilizator Brz_VladBrezae Vlad Brz_Vlad Data 28 decembrie 2012 18:22:26
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.15 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

using namespace std;

#ifndef M_PI
#define M_PI 3.141592654
#endif

typedef struct Point{
	double x;
	double y;
	double angle;
}Point;

double get_angle(double x1, double y1, double x2, double y2)
{
	if( x1 == x2 )
		return M_PI/2;
	else
		return atan((y2-y1)/(x2-x1));
}

double get_angle(Point p1, Point p2)
{
	return get_angle(p1.x,p1.y,p2.x,p2.y);
}

//////////// STACK //////////////////////

typedef struct tagNode
{
	Point value;
	struct tagNode *next;
}Node;

struct Stack
{
	Node* start;
	
	Stack(){
		this->start = NULL;
	}

	void push(Point value){
		Node *niu = new Node;
		niu->next = this->start;
		niu->value = value;
		this->start = niu;	
	}

	Point top(){
		return this->start->value;
	}

	void pop(){
		Node* toDelete = this->start;
		this->start = this->start->next;
		delete toDelete;
	}

	int isEmptyStack(){
		return this->start == NULL;
	}
};

////////////////////////////////////////

#define MAXN 120000

int N;
Point points[MAXN];

Stack solution;
int count;

int compare(const void *pt1, const void *pt2)
{
	return ((Point*)pt1)->angle < ((Point*)pt2)->angle;
}

int main(int argc, char* argv[])
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	
	scanf("%d",&N);
	int startPos = 0;
	
	int i;
	for(i=0;i<N;i++){
		scanf("%lf %lf",&points[i].x,&points[i].y);
		if( (points[i].x < points[startPos].x) ||
			(points[i].x == points[startPos].x && points[i].y < points[startPos].y))
			startPos = i;
	}
	
	Point aux = points[startPos];
	points[startPos] = points[0];
	points[0] = aux;
	
	for(i=1;i<N;i++){
		points[i].angle = get_angle(points[0],points[i]);
	}
	
	qsort(points+1,N-1,sizeof(Point),compare);

	solution.push(points[0]);
	solution.push(points[1]);
	count = 2;
	
	for(i=2;i<N;i++){
#define p1 (solution.start->next->value)
#define p2 (solution.start->value)
#define p3 (points[i])
		while( (p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x) > 1 ){
			solution.pop();
			count--;
		}
		
		solution.push(points[i]);
		count++;		
	}
	printf("%d\n",count);
	Node* q = solution.start;
	while(q != NULL){
		printf("%lf %lf\n",q->value.x,q->value.y);
		q=q->next;
	}
		
	return 0;
}