Pagini recente » Cod sursa (job #1108005) | Cod sursa (job #2637899) | Cod sursa (job #1074060) | Cod sursa (job #233423) | Cod sursa (job #3288359)
#include <fstream>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");
#define oo 1000000000
struct punct
{
double x, 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;
}
int orientation(punct a, punct b, punct c)
{
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
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()
{
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]); // Swap the start point to the first position
sort(v + 1, v + n, cmp); // Sort by angle relative to the start point
vector<int> ras;
ras.push_back(0); // Add the start point to the convex hull
for (int i = 1; i < n; i++)
{
// Print for debugging the sorted points
cout << "Checking point: (" << v[i].x << ", " << v[i].y << ")\n";
// Backtrack if the turn is clockwise (orientation < 0)
while (ras.size() > 2 && orientation(v[ras[ras.size() - 2]], v[ras[ras.size() - 1]], v[i]) < 0)
{
cout << "Popping point: (" << v[ras[ras.size() - 1]].x << ", " << v[ras[ras.size() - 1]].y << ")\n";
ras.pop_back();
}
// Add current point to the convex hull
ras.push_back(i);
}
// Output the number of points on the convex hull
fout << ras.size() << '\n';
// Output the points on the convex hull
for (auto i : ras)
{
fout << v[i].x << " " << v[i].y << '\n';
}
return 0;
}