Pagini recente » Cod sursa (job #1411549) | Cod sursa (job #261394) | Cod sursa (job #800433) | Cod sursa (job #1679418) | Cod sursa (job #1668408)
//JARVIS MARCH
#include<fstream>
#include<vector>
#include<iomanip>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int N;
typedef pair<double, double> POINT2D;
#define x first
#define y second
POINT2D v[120010];
vector<POINT2D> vec;
double crossprod2D(const POINT2D &p1,const POINT2D &p2, const POINT2D &p3)
{
return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x);
}
int main()
{
in >> N;
for (int i = 1;i <= N;++i)
in >> v[i].x >> v[i].y;
double y_min = v[1].y;
int el=1;
for (int i = 2;i <= N;++i)
if (v[i].y < y_min)
{
el = i;
y_min = v[i].y;
}
swap(v[el], v[1]);
vec.push_back(v[1]);
int i;
for (i = 1;i <= N - 2;++i)
{
el = i + 1;
for (int j = i + 2;j <= N;++j)
if (crossprod2D(v[i], v[el], v[j]) < 0)
el = j;
swap(v[el], v[i + 1]);
if (crossprod2D(v[i], v[i+1], v[1]) < 0)
break;
vec.push_back(v[i + 1]);
}
if (i == N - 1)
vec.push_back(v[N]);
out << vec.size() << '\n';
for (int i = 0;i < vec.size();++i)
out <<setprecision(12)<<fixed<< vec[i].x << " " << vec[i].y << '\n';
}