Pagini recente » Cod sursa (job #2240250) | Cod sursa (job #2098495) | Cod sursa (job #2677974) | Cod sursa (job #1511883) | Cod sursa (job #2848712)
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
ifstream file_in("infasuratoare.in");
ofstream file_out("infasuratoare.out");
unsigned int i;
bool C[120005];
struct Point
{ double X, Y; }
P[120005] = { 1000000005 };
vector<int> ConvexHull;
int main()
{
int N; file_in >> N;
for (i = 1; i <= N; ++i)
file_in >> P[i].X >> P[i].Y;
int InitPoint = 0;
for (i = 1; i <= N; ++i)
if (P[i].X < P[InitPoint].X) InitPoint = i;
int CurrentPoint = InitPoint, NewPoint;
double TempPoint, Angle, LastPoint = 0;
bool FirstPoint = true;
while (FirstPoint || InitPoint != CurrentPoint)
{
NewPoint = CurrentPoint;
FirstPoint = false;
TempPoint = 10000;
ConvexHull.push_back(CurrentPoint);
for (i = 1; i <= N; ++i)
{
if (C[i] || i == CurrentPoint) continue;
Angle = atan2(P[i].X - P[CurrentPoint].X, P[i].Y - P[CurrentPoint].Y);
if (Angle < 0) Angle += 2 * M_PI;
Angle -= LastPoint;
if (Angle < 0) Angle += 2 * M_PI;
if (Angle < TempPoint)
TempPoint = Angle, NewPoint = i;
}
LastPoint = atan2(-(P[CurrentPoint].X - P[NewPoint].X), -(P[CurrentPoint].Y - P[NewPoint].Y));
if (LastPoint < 0) LastPoint += 2 * M_PI;
CurrentPoint = NewPoint;
C[CurrentPoint] = true;
}
reverse(ConvexHull.begin(), ConvexHull.end());
file_out << ConvexHull.size() << '\n';
for (i = 0; i < ConvexHull.size(); ++i)
file_out << fixed << setprecision(6) << P[ConvexHull[i]].X << ' ' << P[ConvexHull[i]].Y << '\n';
return 0;
}