Pagini recente » Cod sursa (job #2745551) | Cod sursa (job #1662970) | Cod sursa (job #1400804) | Cod sursa (job #3179878) | Cod sursa (job #2974026)
#include <fstream>
#include <assert.h>
#include <iomanip>
#include <vector>
#include <queue>
#define NMAX 120005
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Punct{
float x,y;
};
int N;
Punct points[NMAX];
int orientation(Punct p, Punct q, Punct r)
{
int val = (q.y - p.y) * (r.x - q.x) -
(q.x - p.x) * (r.y - q.y);
if (val == 0) return 0; // colineare
return (val > 0)? 1: 2; // sens orar : trigonometric
}
void convexHull(Punct points[], int n)
{
vector<Punct> hull;
// Cel mai din stanga punct
int l = 0;
for (int i = 1; i < n; i++)
if (points[i].x < points[l].x)
l = i;
/* Incepeti din punctul cel mai din stanga, continuati sa va miscati in sens trigonometric pana ajungem din nou la punctul de pornire. */
int p = l, q;
do
{
// Add current point to result
hull.push_back(points[p]);
/*
Cautati un punct 'q' astfel incat orientarea (p, q,x) sa fie in sens invers acelor de ceasornic pentru toate punctele 'x'. Ideea este de a tine evidenta ultimului punct cel mai vizitat in sens invers acelor de ceasornic din q. Daca orice punct 'i' este mai in sens invers acelor de ceasornic decat q, atunci actualizati q.
*/
q = (p+1)%n;
for (int i = 0; i < n; i++)
{
if (orientation(points[p], points[i], points[q]) == 2)
q = i;
}
p = q;
} while (p != l); // While we don't come to first point
fout<<hull.size()<<'\n';
for (int i = 0; i < hull.size(); i++)
fout << setprecision(7) << fixed << hull[i].x << " " << hull[i].y << "\n";
}
int main(){
fin>>N;
assert(3<= N && N <= 120000);
for(int i=0;i<N;i++){
fin>>points[i].x>>points[i].y;
}
convexHull(points,N);
return 0;
}