Cod sursa(job #1802932)

Utilizator Etienne27Stefan Etienne27 Data 10 noiembrie 2016 20:03:50
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
FILE*fin = fopen("infasuratoare.in", "r");
FILE*fout = fopen("infasuratoare.out", "w");
struct Point
{
	double x, y;
};
bool sign(const Point* p1,const Point* p2,const Point* p3)
{
	return (p1->x*p2->y + p2->x*p3->y + p3->x*p1->y - p1->x*p3->y - p2->x*p1->y - p3->x*p2->y) > 0;
}
Point* startPoint;
bool myComp1(const Point* my,const Point* other)
{
	return sign(startPoint, my, other) == false;
}
bool myComp2(const Point* my, const Point* other)
{
	return my->y<other->y;
}
int main()
{
	int nrOfPoints;
	double p=100;
	vector<Point*> points,hull;
	Point* current,low;
	fscanf(fin,"%d", &nrOfPoints);
	low.x = 100;
	low.y = 100;
	for (int i = 0; i < nrOfPoints; i++)
	{
		current = new Point;
		fscanf(fin, "%lf %lf", &current->x, &current->y);
		if (low.y<current->y)
		{
			low.y = current->y;
			low.x = current->x;
		}
		points.push_back(current);
	}

	sort(points.begin(), points.end(),myComp2);

	startPoint = new Point;
	startPoint->x = points[0]->x;
	startPoint->y = points[0]->y;

	sort(points.begin()+1, points.end(), myComp1);

	hull.push_back(startPoint);
	hull.push_back(points[1]);

	for (auto it = points.begin() + 2; it != points.end(); it++)
	{
		auto second = hull.end() - 2;
		auto first = hull.end() - 1;
		while (sign(*second, *first, *it) == true)
		{
			hull.erase(first);
			first = second;
			second --;
		}
		hull.push_back(*it);
	}

	int pos = 0;
	for (auto i : hull)
	{
		if (i->y == p)
			pos++;
	}


	std::rotate(hull.begin(), hull.begin() + pos+1, hull.end());
	fprintf(fout, "%d\n", hull.size());
	for (auto i=hull.rbegin();i!=hull.rend();i++)
	{
		fprintf(fout,"%lf %lf\n", (*i)->x, (*i)->y);
	}
}