Cod sursa(job #3030624)

Utilizator thinkphpAdrian Statescu thinkphp Data 17 martie 2023 19:21:11
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <stdio.h>
#include <algorithm>

#define DIM 150005
#define inf 1<<30

using namespace std;

int n, i, j, level, pointMin;
int Stack[ DIM ];
double xmin, ymin = inf, A;


struct Point{
	double x, 
	       y;
} Arr[DIM], aux;


int comp(Point a, Point b){
	return a.x * b.y >= b.x * a.y;
}

int convex (Point a, Point b, Point c){
	
	A = a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
	if (A > 0) 
		return 1;
	return 0;
	
}

int main (){
	
	FILE * f = fopen ("infasuratoare.in", "r");
	FILE * g = fopen ("infasuratoare.out", "w");
	
	fscanf (f, "%d", &n);
	for (i = 1 ; i <= n ; i++){
		fscanf(f, "%lf %lf", &Arr[i].x, &Arr[i].y);
		if (ymin > Arr[i].y){
			xmin = Arr[i].x;
			ymin = Arr[i].y;
			pointMin = i;	
		}
	}
	
	for (i = 1 ; i <= n ; i++){
		Arr[i].x -= xmin;
		Arr[i].y -= ymin;
	}
	
	aux = Arr[1];
	Arr[1] = Arr[pointMin];
	Arr[pointMin] = aux;

	sort (Arr+2, Arr+n+1, comp); 
	
	
	Stack[1] = 1;
	Stack[2] = 2;
	level = 2;
	
	for (i = 3 ; i <= n ; i++){
		while ( level >= 3 && !convex(Arr[Stack[level-1]], Arr[Stack[level]], Arr[i]) )
			level --;
		
		Stack[++level] = i;
	}
	
	fprintf (g, "%d\n", level);
	for (i = 1 ; i <= level ; i++) 
		fprintf (g, "%lf %lf\n", Arr[Stack[i]].x + xmin, Arr[Stack[i]].y + ymin);	
	
	fclose(f);
	fclose(g);
	return 0; 
}