Pagini recente » Cod sursa (job #2625099) | Cod sursa (job #2691083) | Cod sursa (job #3279897) | Cod sursa (job #3290860) | Cod sursa (job #3288354)
#include <fstream>
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define oo 1000000000
struct punct
{
double x;
double y;
} v[120005];
bool smaller(punct x, punct y)
{
if (x.y < y.y)
{
return true;
}
if (x.y == y.y)
{
return x.x < y.x;
}
return false;
}
double distance(punct a, punct b)
{
return sqrt((b.y - a.y) * (b.y - a.y) + (b.x - a.x) * (b.x - a.x));
}
int orientation(punct a, punct b, punct c)
{
// diferenta dintre panta dreptelor
// c.y-b.y/c.x-b.x - b.y-a.y/b.x-a.x
int d = (c.y - b.y) * (b.x - a.x) - (b.y - a.y) * (c.x - b.x);
if (d > 0)
return 1;
if (d < 0)
return -1;
// d==0
return 0;
}
double angle(punct a, punct b)
{
return atan2(b.y - a.y, b.x - a.x);
}
bool cmp(punct a, punct b)
{
return angle(v[0], a) < angle(v[0], b);
}
int main()
{
// cout << angle({0, 0}, {1, 1});
int n;
fin >> n;
punct start;
int istart;
start.x = oo;
start.y = oo;
for (int i = 0; i < n; i++)
{
fin >> v[i].x >> v[i].y;
if (smaller(v[i], start))
{
start = v[i];
istart = i;
}
}
swap(v[istart], v[0]);
sort(v + 1, v + n, cmp);
// for (int i = 0; i < n; i++)
// {
// fout << v[i].x << " " << v[i].y << '\n';
// }
vector<int> ras;
ras.push_back(0);
int size = 1;
for (int i = 1; i < n; i++)
{
if (ras.size() > 2 && orientation(v[ras[ras.size() - 2]], v[ras[ras.size() - 1]], v[i]) != 1)
{
ras.erase(ras.begin() + ras.size() - 1);
}
ras.push_back(i);
}
fout << ras.size() << '\n';
for (auto i : ras)
{
fout << v[i].x << " " << v[i].y << '\n';
}
return 0;
}