Cod sursa(job #2310848)

Utilizator cezar.plescaCezar Plesca cezar.plesca Data 2 ianuarie 2019 11:03:19
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.77 kb
#include<stdio.h>
#include <math.h>
#include <algorithm>
 
using namespace std;

typedef struct point{
	double x;
	double y;
	double cos;
}point;

// Three points are a counter-clockwise turn if ccw > 0, clockwise if
// ccw < 0, and collinear if ccw = 0 because ccw is a determinant that
// gives twice the signed  area of the triangle formed by p1, p2 and p3.
double ccw(point & p1, point & p2, point & p3){
    return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x);
}

#define MAXN 120000

int N;
 
point P[MAXN]; 
int S[MAXN];
int lS;

bool sortByAngle(const point &lhs, const point &rhs) {
	return lhs.cos > rhs.cos; 
}

void complexhull(){
	S[0]=0;
	S[1]=1;
	lS=2;
	double sens;
	for(int i=2; i<N ; i++){
		while(lS>=2){
			sens=ccw(P[S[lS-2]], P[S[lS-1]], P[i]);
			if(sens <= 0){
				// pop operation
				lS--;
			}
			else
				break;
		}
		S[lS]=i;
		lS++;
	}
}

int main(void){
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);

	scanf("%d",&N);

	double x,y;
	scanf("%lf %lf",&x,&y);
	P[0].x=x; P[0].y=y;
	double miny=y;
	double minx=x;
	int index=0;
	for(int i=1;i<N;i++){
		scanf("%lf %lf",&x,&y);
		P[i].x=x; P[i].y=y;
		if(y<miny){
			miny=y;
			minx=x;
			index=i;
		}
		else{
			if(y==miny && x<minx){
				minx=x;
				index=i;
			}	
		}
	}

	point Q(P[0]);
	P[0].x=P[index].x;
	P[0].y=P[index].y;
	P[index].x=Q.x;
	P[index].y=Q.y;
	
	double r;
	for(int i=1;i<N;i++){
		r=(P[i].x-P[0].x)*(P[i].x-P[0].x);
		r+=(P[i].y-P[0].y)*(P[i].y-P[0].y);
		r=sqrt(r);
		P[i].cos=(P[i].x-P[0].x)/r;
	}

	sort(P + 1, P + N, sortByAngle);
	
	complexhull();

	printf("%d\n",lS);
	for(int i=0;i<lS;i++){
		printf("%lf %lf\n",P[S[i]].x,P[S[i]].y);	
	}
    
    return 0;
}