Pagini recente » Cod sursa (job #2608347) | Cod sursa (job #2421001) | Cod sursa (job #663718) | Cod sursa (job #2203167) | Cod sursa (job #2854321)
#include <bits/stdc++.h>
using namespace std;
/*******************************/
// INPUT / OUTPUT
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
/*******************************/
/// GLOBAL DECLARATIONS
int N;
int nr = 2;
struct Point
{
long double x, y;
} p0;
stack <int> s;
vector <Point> points, ans;
/*******************************/
/// FUNCTIONS
void ReadInput();
void Solution();
void Output();
/*******************************/
///-------------------------------------
inline void ReadInput()
{
f >> N;
long double x, y;
for (int i = 0 ; i < N ; ++ i)
{
f >> x >> y;
points.push_back({x, y});
}
}
///-------------------------------------
int Orientation(const Point &p0, const Point &p1, const Point &p2)
{
long double val = (p1.y - p0.y) * (p2.x - p1.x) - (p1.x - p0.x) * (p2.y - p1.y);
if (val == 0) return 0; // collinear
if (val > 0) return 1; // clockwise
return -1; // counter-clockwise
}
///-------------------------------------
long double DistSqrd(const Point &p1, const Point &p2)
{
return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}
///-------------------------------------
bool comp(const Point &p1, const Point &p2)
{
int o = Orientation(p0, p1, p2);
if (o == 0) // Points are collinear
{
return DistSqrd(p0, p1) <= DistSqrd(p0, p2);
}
if (o == 1) return 0;
return 1;
}
///-------------------------------------
inline void Solution()
{
long double minY = points[0].y, minPoint = 0;
for (int i = 1 ; i < N ; ++ i)
{
if ((points[i].y < minY) || (points[i].y == minY && points[i].x < points[minPoint].x))
{
minY = points[i].y;
minPoint = i;
}
}
swap(points[0], points[minPoint]);
p0 = points[0];
sort(points.begin() + 1, points.end(), comp);
ans.push_back(p0);
ans.push_back(points[1]);
for (int i = 2 ; i < N ; ++ i)
{
while (nr > 1 && Orientation(ans[nr - 1], ans[nr - 2], points[i]) != 1)
{
ans.pop_back();
nr --;
}
ans.push_back(points[i]);
nr ++;
}
}
///-------------------------------------
inline void Output()
{
for (int i = 0 ; i < nr ; ++ i)
{
g << fixed << setprecision(6) << ans[i].x << " " << ans[i].y << "\n";
}
}
///-------------------------------------
int main()
{
ReadInput();
Solution();
Output();
return 0;
}