Pagini recente » Cod sursa (job #2505335) | Cod sursa (job #2521403) | Cod sursa (job #1542177) | Cod sursa (job #666015) | Cod sursa (job #2541078)
#include <fstream>
#include <stack>
#include <bitset>
#include <algorithm>
#include <iomanip>
using namespace std;
const int N = 120005;
struct Point
{
double x, y;
bool operator < (const Point &b) const
{
if (this -> y == b.y) return (this -> x < b.x);
return (this -> y < b.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;
}
double Check (int i, int j, Point W)
{
return (a[i].y - a[j].y) * W.x + (a[j].x - a[i].x) * W.y
+ (a[i].x * a[j].y - a[j].x * a[i].y);
}
void Convex_Hull ()
{
sort (a + 1, a + n + 1);
st[1] = 1;
st[2] = 2;
top = 2;
inhull[1] = inhull[2] = 1;
for (int i = 3; i <= n; i++)
{
while (top >= 2 && Check(st[top - 1], 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 >= 2 && Check(st[top - 1], st[top], a[i]) < 0)
{
inhull[st[top]] = 0;
top--;
}
st[++top] = i;
inhull[i] = 1;
}
}
}
void Write ()
{
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";
}
int main()
{
Read();
Convex_Hull();
Write();
return 0;
}