Mai intai trebuie sa te autentifici.
Cod sursa(job #2380337)
Utilizator | Data | 14 martie 2019 20:03:36 | |
---|---|---|---|
Problema | Infasuratoare convexa | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 1.44 kb |
#include <iostream>
#include <fstream>
#include <iomanip>
#define MAXN 120005
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
int n;
typedef pair<double,double> Point;
Point a[MAXN];
Point steve[MAXN];
void citire()
{
fin>>n;
for (int i=1;i<=n;i++)
{
double x,y;
fin>>x>>y;
a[i]=make_pair(x, y);
}
}
double cross_product(Point a,Point b,Point c)
{
return (b.first - a.first) * (c.second - a.second) - (b.second - a.second) * (c.first - a.first);
//If the result is 0, the points are collinear; if it is positive, the three points constitute a "left turn" or counter-clockwise orientation, otherwise a "right turn" or clockwise orientation
}
int cmp(const Point& p1, const Point& p2) {
return cross_product(a[1], p1, p2) < 0;
}
void sort_points() {
int pos = 1;
for (int i = 2; i <= n; ++i)
if (a[i] < a[pos])
pos = i;
swap(a[1], a[pos]);
sort(a + 2, a + n + 1, cmp);
}
void convex_hull()
{
sort_points();
steve[1]=a[1];
steve[2]=a[2];
int vf=2;
for (int i=3;i<=n;i++)
{
while (vf>2&&cross_product(steve[vf-1], steve[vf], a[i])>0)
vf--;
steve[++vf]=a[i];
}
fout<<vf<<'\n';
fout<<setprecision(6)<<fixed;
for (int i=vf;i>=1;i--)
fout<<steve[i].first<<' '<<steve[i].second<<'\n';
}
int main()
{
citire();
convex_hull();
return 0;
}