Cod sursa(job #1040770)

Utilizator miu_mik93FMI - Paduraru Miruna miu_mik93 Data 24 noiembrie 2013 21:54:22
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <string>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <queue>
#include <cstdlib>
#include <iomanip>
using namespace std;

	
#define NMAX 12001
#define EPS 1e-12


struct point 
{
	double x, y;
};

int st[NMAX];
bool viz[NMAX];

int compare(const void *a, const void *b)
{
	point* _a = (point*)a ;
	point* _b = (point*)b;
	if ( _a->x == _b->x )
		return _a->y - _b->y;
	else
		return _a->x - _b->x;
}

double convex (point A, point B, point C)
{
	return (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
}

int main()
{
	int N;
	FILE *f = fopen ("infasuratoare.in", "r");
	FILE *g = fopen ("infasuratoare.out", "w");
	fscanf (f, "%d", &N);

	point v[NMAX];
	//v = new point[N];

	for (int i = 0; i < N; i++)
	{
		fscanf(f, "%lf %lf", &v[i].x, &v[i].y);
	}

	qsort(v, N, sizeof(point), compare);
	
	st[0] = 0; st[1] = 1; int u = 1, p = 0, j = 0;
	viz[1] = 1; int l = 0;
	
	/*while ( j >= 0 )
	{
		if (j == N-1)
		{
			p *= -1;
		} 
		
		j += p;
		
		if ( viz[j] ) continue;
		
		while (u >= 1 && convex(v[st[u-1]], v[st[u]], v[j]) < EPS)
			viz[st[u--]] = 0;
		
		st[++u] = j;
		viz[j] = 1;
		if (j == 0 && l == 0)
		{
			p++;
			l = 1;
		}
	}*/

	  for (int i = 0, p = 1; i >= 0; i += (p = (i == N ? -p : p)))
	  {
        if (viz[i])
			continue;
        while (u >= 2 && convex (v[st[u - 1]], v[st[u]], v[i]) < EPS)
            viz[st[u--]] = false;
        st[++u] = i;
        viz[i] = true;
    }

	fprintf (g, "%d\n", u-1);
	
	for (int i = 0 ; i < u; i++)
		fprintf (g, "%.6lf %.6lf\n", v[st[i]].x, v[st[i]].y);
	
	fclose(f); fclose(g);
	return 0;
}