Pagini recente » Cod sursa (job #676632) | Cod sursa (job #1941953) | Cod sursa (job #2067425) | Cod sursa (job #1265907) | Cod sursa (job #2289266)
#include <cstdio>
#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;
PUNCT Puncte[MAXN];
bool EsteInStiva[MAXN];
int Stiva[MAXN], varf;
int N;
bool cmpPunct(PUNCT, PUNCT);
double Sarrus(PUNCT, PUNCT, PUNCT);
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
/// Citim N si coordonatele punctelor
scanf("%i", &N);
for(int i = 1; i <= N; ++i)
scanf("%lf %lf", &Puncte[i].x, &Puncte[i].y);
/// Sortam punctele dupa Y si, in caz de egalitate, dupa X
sort(Puncte + 1, Puncte + N + 1, cmpPunct);
varf = 2;
Stiva[1] = 1; Stiva[2] = 2;
EsteInStiva[2] = true;
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;
}
}
/// 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);
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 * P2.y + P2.x * P3.y + P3.x * P1.y
-P3.x * P2.y - P2.x * P1.y - P1.x * P3.y;
}
bool cmpPunct(PUNCT X, PUNCT Y)
{
if(X.second == Y.second)
return X.first < Y.first;
return X.second < Y.second;
}