Pagini recente » Cod sursa (job #2870600) | Cod sursa (job #2253817) | Cod sursa (job #2645916) | Cod sursa (job #2958073) | Cod sursa (job #871065)
Cod sursa(job #871065)
// Include
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
using namespace std;
// Definitii
#define mp make_pair
#define point pair<double,double>
#define y first
#define x second
#define leftTurn(a,b,c) (det(a,b,c)>0)
#define prev at(convexHull.size()-2)
#define top at(convexHull.size()-1)
#define pb push_back
#define popb pop_back
// Constante
const int sz = (int)12e4+1;
// Functii
double det(point a, point b, 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; }
// Variabile
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int num;
point points[sz];
point minPoint, current;
vector<point> convexHull;
class byAngle
{
public:
bool operator() (point a, point b)
{ return leftTurn(minPoint, a, b); }
};
// Main
int main()
{
out << fixed << setprecision(6);
in >> num;
in >> minPoint.x >> minPoint.y;
for(int i=1 ; i<num ; ++i)
{
in >> current.x >> current.y;
if(current < minPoint)
{
points[i] = minPoint;
minPoint = current;
}
else
points[i] = current;
}
sort(points+1, points+num, byAngle());
convexHull.reserve(num);
convexHull.pb(minPoint);
convexHull.pb(points[1]);
for(int i=2 ; i<num ; ++i)
{
while(!leftTurn(convexHull.prev, convexHull.top, points[i]))
convexHull.popb();
convexHull.pb(points[i]);
}
out << convexHull.size() << '\n';
vector<point>::iterator it, end=convexHull.end();
for(it=convexHull.begin() ; it!=end ; ++it)
out << it->x << ' ' << it->y << '\n';
in.close();
out.close();
return 0;
}