Pagini recente » Cod sursa (job #1092210) | Cod sursa (job #3131647) | Cod sursa (job #1313677) | Cod sursa (job #2075288) | Cod sursa (job #3281173)
#include <fstream>
#include <iostream>
#include <vector>
#include <bitset>
#include <set>
#include <stack>
#include <algorithm>
#include <iomanip>
using namespace std;
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;
}
}a[120001];
int n;
int st[120001], top;
bitset <120001> inhull;
void Read()
{
ifstream fin("infasuratoare.in");
fin >> n;
for (int i = 1; i <= n; i++)
fin >> a[i].x >> a[i].y;
}
bool isLeft(Point a, Point b, Point c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x) > 0;
}
void ConvexHull() {
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 && !isLeft(a[st[top - 1]], a[st[top]], a[i]))
{
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 && !isLeft(a[st[top - 1]], a[st[top]], a[i]))
{
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(6) << fixed << a[st[i]].x << " " << a[st[i]].y << "\n";
}
int main()
{
Read();
ConvexHull();
Write();
return 0;
}