Cod sursa(job #1356960)

Utilizator anaid96Nasue Diana anaid96 Data 23 februarie 2015 17:55:34
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include<stdio.h>
#include<vector>
#include<utility>
#include<algorithm>

using namespace std;

FILE *in, *out;

//defintions
#define pb push_back
#define x first
#define y second
#define prev at(infas.size()-2)
#define top at(infas.size()-1)

//constants

//variables
int nPoints;

pair<double,double> minimum, point;

vector<pair<double, double> > points, infas;

//functions
bool angle(pair<double, double> a, pair<double, double> b);
double det(pair<double, double> a, pair<double, double> b, pair<double, double> c);

int main(void)
{
	in = fopen("infasuratoare.in", "rt");
	out = fopen("infasuratoare.out", "wt");
	
	fscanf(in, "%d", &nPoints);
	
	points.reserve(nPoints);	
	infas.reserve(nPoints);
	
	fscanf(in, "%lf%lf", &minimum.x, &minimum.y);
	
	for(int i=1; i<nPoints; ++i)
	{
		fscanf(in, "%lf%lf", &point.x, &point.y);
		
		if(point < minimum)
		{
			points.pb(minimum);
			minimum = point;
		}
		else
			points.pb(point);
	}
	
	sort(points.begin(), points.end(), angle);
	
	vector<pair<double, double> > :: iterator it=points.begin(), end=points.end();
	
	infas.pb(minimum);
	infas.pb(*it++);
	
	for(; it!=end; ++it)
	{
		while( det(infas.prev, infas.top, *it) < 0)
			infas.pop_back();
		infas.pb(*it);
	}
	
	fprintf(out, "%d\n", infas.size());
	
	it = infas.begin() , end=infas.end();
	
	for(; it!=end; ++it)
		fprintf(out, "%lf %lf\n", it->x, it->y);
	
	fclose(in);
	fclose(out);
	return 0;
}


bool angle(pair<double, double> a, pair<double, double> b)
{
	return det(minimum, a, b)>0;
}
double det(pair<double, double> a, pair<double, double> b, pair<double, double> c)
{
	return a.x*b.y + c.x*a.y + b.x*c.y - b.y*c.x - a.y*b.x - a.x*c.y; 
}