Pagini recente » Cod sursa (job #2280287) | Cod sursa (job #90872) | Cod sursa (job #510263) | Cod sursa (job #2001616) | Cod sursa (job #758131)
Cod sursa(job #758131)
//Include
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;
//Definitii
#define t_point pair<double, double>
#define y first
#define x second
#define mp make_pair
#define pb push_back
#define top at(convexHull.size()-1)
#define prev at(convexHull.size()-2)
#define pop pop_back
#define leftTurn(a,b,c) (det(a,b,c)>0)
//Functii
double det(t_point a, t_point b, t_point c);
//Variabile
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int pointsNumber;
t_point minPoint, tempPoint;
vector<t_point> points, convexHull;
//Clase de sortare
class byAngle
{
public:
bool operator() (t_point a, t_point b)
{ return leftTurn(minPoint, a, b); }
};
//Main
int main()
{
in >> pointsNumber >> minPoint.x >> minPoint.y;
points.reserve(pointsNumber);
convexHull.reserve(pointsNumber);
out << fixed << setprecision(6);
for(int i=1 ; i< pointsNumber ; ++i)
{
in >> tempPoint.x >> tempPoint.y;
if(tempPoint < minPoint)
{
points.pb(minPoint);
minPoint = tempPoint;
}
else
points.pb(tempPoint);
}
sort(points.begin(), points.end(), byAngle());
vector<t_point>::iterator it=points.begin(), end=points.end();
convexHull.pb(minPoint);
convexHull.pb(*it++);
for(; it!=end ; ++it)
{
while(!leftTurn(convexHull.prev, convexHull.top, *it))
convexHull.pop();
convexHull.pb(*it);
}
it = convexHull.begin(); end = convexHull.end();
out << convexHull.size() << '\n';
for(; it!=end ; ++it)
out << it->x << ' ' << it->y << '\n';
in.close();
out.close();
return 0;
}
double det(t_point a, t_point b, t_point c)
{ return a.x*b.y + b.x*c.y + c.x*a.y - a.y*b.x - b.y*c.x - c.y*a.x; }