Cod sursa(job #2545459)

Utilizator Idk.Voicu Stefan Idk. Data 13 februarie 2020 09:29:50
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include<stdio.h>
#include<algorithm>
#include <stdio.h>
#define nmax 120010
#define INF 1<<30 //2 la 30
using namespace std;

int i,n,k,s[nmax],poz;

struct punct
{
	double x,y,panta;
} v[nmax],o,aux;

int cmp ( punct a, punct b)
{
	if(a.panta==b.panta) return a.x<b.x;

	return a.panta<b.panta;
}

int convex()
{
	punct a,b,c;
	double nr;

	a=v[s[k-1]];
	b=v[s[k]];
	c=v[i];

	nr = ( a.x-c.x ) * ( b.y-a.y ) + ( a.x-b.x ) * ( a.y-c.y ) ;

	if(nr > 0) {
        return 1;
	}
	return 0;
}


int main()
{
	FILE*in = fopen("infasuratoare.in", "r");
	FILE*out = fopen("infasuratoare.out", "w");

	fscanf(in, "%d",&n);

	o.x=o.y=INF;

	for(i = 1;i <= n; i++)
	{
		fscanf(in, "%lf %lf",&v[i].x,&v[i].y);

		if(v[i].x < o.x || v[i].x == o.x && v[i].y < o.y) {
			o=v[i];
			poz=i;
		}
	}

	aux=v[1]; v[1]=v[poz]; v[poz]=aux;

	for(i = 2; i <= n; i++) {
		v[i].panta = (v[i].y - o.y)/(v[i].x - o.x);
	}
	sort(v+2, v+n+1, cmp);

	s[1]=1; s[2]=2; k=2;

	for(i=3;i<=n;i++)
	{
		while (!convex() && k>2) {
            k--;
		}
		s[++k]=i;
	}

	fprintf(out, "%d\n",k);

	for(i=1;i<=k;i++)
		fprintf(out, "%0.6lf %0.6lf\n",v[s[i]].x,v[s[i]].y);
	return 0;
}