Pagini recente » Cod sursa (job #597448) | Cod sursa (job #2274833) | Cod sursa (job #62065) | Cod sursa (job #872089) | Cod sursa (job #2368669)
#include <bits/stdc++.h>
#define nmax 120007
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
int n;
struct Punct
{
double x, y;
};
Punct a[nmax];
bool viz[nmax];
int st[nmax], top;
void Citire()
{
int i;
fin >> n;
for (i = 1; i <= n; i++)
fin >> a[i].x >> a[i].y;
}
double Determinant(int A, int B, int C)
{
return ((a[A].x * a[B].y) + (a[B].x * a[C].y) + (a[C].x * a[A].y)
- (a[B].y * a[C].x) - (a[C].y * a[A].x) - (a[A].y * a[B].x));
}
/// Se sortează punctele după abscisă și, în caz de egalitate după ordonată.
inline bool Compar(const Punct A, const Punct B)
{
if (A.y == B.y) return A.x < B.x;
return A.y < B.y;
}
void Rezolvare()
{
sort (a + 1, a + n + 1, Compar);
/// Se aleg ca puncte de pornire primul și al doilea punct din sortare.
st[++top] = 1;
st[++top] = 2;
viz[1] = viz[2] = true;
/**
Vom considera apoi punctele următoare în ordinea sortării. Dacă Pi-2
este penultimul punct din stivă, Pi-1 este ultimul, iar Pi este punctul
curent, vom verifica dacă unghiul format de cele 3 puncte nu anulează
conexitatea. Practic acest unghi trebuie să reprezinte o întoarcere spre
dreapta. Verificarea se va face cu ajutorul semnului determinantului
acest este pozitiv, Pi se află de partea greșită a dreptei ce trece prin
folosit pentru calculul ariei triunghiului format de cele 3 puncte. Dacă
Pi-2, Pi-1 și atunci eliminăm punctul care încalcă conexitatea, și anume
Pi-1. Continuăm această verificare până eliminăm toate punctele din stivă
care încalcă conexitatea și repetăm procedeul până când ajungem de unde
am pornit.
*/
for (int i = 3; i <= n; i++)
{
while ((Determinant(st[top - 1], st[top], i) < 0) && (top > 1))
{
viz[st[top]] = 0;
top--;
}
st[++top] = i;
viz[i] = 1;
}
/**
Algoritmul are două faze, când testăm punctele de la 3 până la i, și a doua
fază,considerarea punctelor neintroduse în stivă, de la n la 2. În final,
stiva va reține punctele de pe înfășurătoare în ordinea invers trigonometrică.
*/
viz[1] = 0;
for (int i = n - 1; i >= 1; i--)
{
if (viz[i] == 0)
{
while (Determinant(st[top - 1], st[top], i) < 0)
{
viz[st[top]] = 0;
top--;
}
st[++top] = i;
viz[i] = 1;
}
}
}
void Afisare()
{
int i;
fout << (top - 1) << "\n";
for (i = 1; i < top; i++)
fout << setprecision(12) << fixed << a[st[i]].x << " " << a[st[i]].y << "\n";
}
int main()
{
Citire();
Rezolvare();
Afisare();
fin.close();
fout.close();
return 0;
}