Cod sursa(job #1928281)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 16 martie 2017 00:00:54
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#define MaxN 120005
#define PI 3.141592
using namespace std;

FILE*IN,*OUT;

int N,Lower[MaxN],Upper[MaxN],UpSize=1,LowSize=1;
struct Point
{
	double x,y;
}v[MaxN];
bool cond(Point a,Point b)
{
	return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
double Angle(int x,int y)
{
		return atan2(v[x].y-v[y].y,v[x].x-v[y].x);
}
int main()
{
    IN=fopen("infasuratoare.in","r");
    OUT=fopen("infasuratoare.out","w");

	fscanf(IN,"%d",&N);

	for(int i=1;i<=N;i++)
		fscanf(IN,"%lf%lf",&v[i].x,&v[i].y);
	sort(v+1,v+1+N,cond);
	Lower[1]=Upper[1]=1;
	for(int i=2;i<=N;i++)
	{
		while(UpSize>1&&Angle(i,Upper[UpSize])-Angle(Upper[UpSize],Upper[UpSize-1])>0)
			UpSize--;
		Upper[++UpSize]=i;
		while(LowSize>1&&Angle(i,Lower[LowSize])-Angle(Lower[LowSize],Lower[LowSize-1])<0)
			LowSize--;
		Lower[++LowSize]=i;
	}
	fprintf(OUT,"%d\n",UpSize+LowSize-2);
	for(int i=1;i<=LowSize;i++)
		fprintf(OUT,"%lf %lf\n",v[Lower[i]].x,v[Lower[i]].y);
	for(int i=UpSize-1;i>1;i--)
		fprintf(OUT,"%lf %lf\n",v[Upper[i]].x,v[Upper[i]].y);
    return 0;
}