Pagini recente » Cod sursa (job #1375990) | Cod sursa (job #180399) | Cod sursa (job #1636191) | Cod sursa (job #600912) | Cod sursa (job #2289260)
#include <cstdio>
#include <algorithm>
using namespace std;
#define x first
#define y second
typedef pair < double, double > PUNCT;
const int MAXN = 120000 + 16;
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 = 1;
Stiva[1] = 1;
EsteInStiva[1] = 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]) < 0)
EsteInStiva[Stiva[varf--]] = false;
Stiva[++varf] = i;
EsteInStiva[i] = true;
}
}
/// Afisam solutia
printf("%i\n", varf);
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;
}