Pagini recente » Cod sursa (job #582619) | Cod sursa (job #792597) | Cod sursa (job #2744032) | Cod sursa (job #2703703) | Cod sursa (job #2713057)
#include <bits/stdc++.h>
using namespace std;
/// Convex Hull - O(n log n)
/**
x * (B.y - A.y) + y*(A.x-B.x) + A.y*(B.x-A.x)+A.x*(B.y-A.y) = 0
*/
struct punct
{
double x, y;
};
int st[103], n, top, viz[102];
punct a[102];
bool Cmp(punct A, punct B)
{
if (A.y == B.y) return A.x < B.x;
return A.y < B.y;
}
void Citire()
{
ifstream fin("infasuratoare.in");
fin >> n;
for (int i = 1; i <= n; i++)
fin >> a[i].x >> a[i].y;
fin.close();
}
int F(punct A, punct B, punct C)
{
int rez = C.x * (B.y - A.y) + C.y * (A.x-B.x) +
A.y*(B.x-A.x)-A.x*(B.y-A.y);
if (rez < 0) return -1;
if (rez > 0) return 1;
return 0;
}
void Convex_Hull()
{
int i;
sort(a + 1, a + n + 1, Cmp);
top = 0;
st[++top] = 1;
st[++top] = 2;
viz[1] = viz[2] = 1;
for (i = 3; i <= n; i++)
{
while (top >= 2 && F(a[st[top-1]], a[st[top]], a[i]) > 0)
{
viz[ st[top] ] = 0;
top--;
}
st[++top] = i;
viz[i] = 1;
}
/// parcurgem punctele nevizitate de la n la 1
viz[1] = 0;
for (i = n; i >= 1; i--)
if (viz[i] == 0)
{
while (top >= 2 && F(a[st[top-1]], a[st[top]], a[i]) > 0)
{
viz[ st[top] ] = 0;
top--;
}
st[++top] = i;
viz[i] = 1;
}
top--;
}
void Afisare()
{
ofstream fout("infasuratoare.out");
fout << top << "\n";
for (int i = 1; i <= top; i++)
fout << fixed << setprecision(12) << a[st[i]].x << " " << a[st[i]].y << "\n";
fout.close();
}
int main()
{
Citire();
Convex_Hull();
Afisare();
return 0;
}