Pagini recente » Cod sursa (job #531539) | Cod sursa (job #1348629) | Cod sursa (job #1713053) | Cod sursa (job #409928) | Cod sursa (job #2289285)
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define x first
#define y second
typedef pair < double, double > PUNCT;
const int MAXN = 120000 + 16;
const double EPS = 1e-12;
int N;
PUNCT Puncte[MAXN];
bool EsteInStiva[MAXN];
int Stiva[MAXN], varf;
void citire();
void afisare();
bool cmpPunct(PUNCT, PUNCT);
double Sarrus(PUNCT, PUNCT, PUNCT);
int main()
{
citire();
/// Sortam punctele dupa X si, in caz de egalitate, dupa Y
sort(Puncte + 1, Puncte + N + 1, cmpPunct);
varf = 1;
Stiva[1] = 1;
for(int i = 1, p = 1; i > 0; i += (p = (i == N ? -p : p)))
{
if(!EsteInStiva[i])
{
/// Vrem sa adaugam i in infasuratoare, asa ca vom elimina toate punctele
/// precedente ce formeaza o concavitate
while(varf >= 2 && Sarrus(Puncte[Stiva[varf - 1]], Puncte[Stiva[varf]], Puncte[i]) < EPS)
EsteInStiva[Stiva[varf--]] = false;
Stiva[++varf] = i;
EsteInStiva[i] = true;
}
}
afisare();
return 0;
}
/**
Numar positiv -> Punct 3 se afla in stanga vectorului P1P2
Numar negativ -> Punct 3 se afla in dreapta vectorului P1P2
| P1.x P1.y 1 |
| P2.x P2.y 1 |
| P3.x P3.y 1 |
**/
double Sarrus(PUNCT P1, PUNCT P2, PUNCT P3)
{
return (P1.x - P3.x) * (P2.y - P3.y) - (P2.x - P3.x) * (P1.y - P3.y);
}
bool cmpPunct(PUNCT X, PUNCT Y)
{
if(X.first == Y.first)
return X.second < Y.second;
return X.first < Y.first;
}
void citire()
{
freopen("infasuratoare.in", "r", stdin);
/// Citim N si coordonatele punctelor
scanf("%i", &N);
for(int i = 1; i <= N; ++i)
scanf("%lf %lf", &Puncte[i].x, &Puncte[i].y);
fclose(stdin);
}
void afisare()
{
freopen("infasuratoare.out", "w", stdout);
/// Afisam solutia
printf("%i\n", varf - 1);
for(int i = 1; i < varf; ++i)
printf("%.6lf %.6lf\n", Puncte[Stiva[i]].x, Puncte[Stiva[i]].y);
fclose(stdout);
}