Pagini recente » Cod sursa (job #2350603) | Cod sursa (job #2808612) | Cod sursa (job #544626) | Cod sursa (job #1000352) | Cod sursa (job #2567717)
#include <fstream>
#include <iostream>
#include <stack>
#include <algorithm>
#include <bitset>
#include <iomanip>
using namespace std;
const int N = 120005;
struct Point
{
double x, y;
bool operator < (const Point other) const
{
if (this -> y == other.y) return (this -> x < other.x);
return (this -> y < other.y);
}
};
Point a[N];
int n, st[N], top;
bitset <N> inhull;
void Read ()
{
ifstream fin ("infasuratoare.in");
fin >> n;
for (int i = 1; i <= n; i++)
fin >> a[i].x >> a[i].y;
fin.close();
}
double Check_Plane (Point A, Point B, Point C) ///Point C in relation to line AB
{
return A.y * (C.x - B.x) + C.y * (B.x - A.x) + B.y * (A.x - C.x);
}
void Convex_Hull ()
{
sort(a + 1, a + n + 1);
top = 2;
st[1] = 1;
st[2] = 2;
inhull[1] = inhull[2] = 1;
for (int i = 3; i <= n; i++)
{
while (top > 1 && Check_Plane(a[st[top - 1]], a[st[top]], a[i]) < 0)
{
inhull[st[top]] = 0;
top--;
}
st[++top] = i;
inhull[i] = 1;
}
inhull[1] = 0;
for (int i = n; i >= 1; i--)
{
if (!inhull[i])
{
while (top > 1 && Check_Plane(a[st[top - 1]], a[st[top]], a[i]) < 0)
{
inhull[st[top]] = 0;
top--;
}
st[++top] = i;
inhull[i] = 1;
}
}
ofstream fout ("infasuratoare.out");
fout << top - 1 << "\n";
for (int i = 1; i < top; i++)
fout << setprecision(12) << fixed << a[st[i]].x << " " << a[st[i]].y << "\n";
fout.close();
}
int main()
{
Read();
Convex_Hull();
return 0;
}