Pagini recente » Cod sursa (job #1305076) | Cod sursa (job #1727751) | Cod sursa (job #432368) | Cod sursa (job #2073807) | Cod sursa (job #2809750)
// complexitate O(Nlog2N), data de sortare
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int N = 1.2e5 + 1;
int n, punct_initial = 1, varf;
pair<double, double> p[N], stiva[N];
inline int produsIncrucisat(pair<double, double> A, pair<double, double> B, pair<double, double> C){
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x); // valoarea componentei pe axa z a lui AB X AC
}
inline bool cmp(pair<double, double> p1, pair<double, double> p2){
return produsIncrucisat(p[1], p1, p2) < 0; // < 0 <=> vectorul (originea in p[1]) cu capatul p2 e in dreapta celui cu capatul p1 (daca consideram axa centrala vectorul cu capatul in p1, p2 e in dreapta lui p1)
}
int main(){
f >> n;
for(int i = 1; i <= n; i++)
f >> p[i].x >> p[i].y;
f.close();
for(int i = 2; i <= n; i++){
if(p[i] < p[punct_initial]) // punctul cel mai din stanga si, in caz de egalitate, cel mai de jos
punct_initial = i;
}
swap(p[1], p[punct_initial]);
sort(p + 2, p + n + 1, cmp);
/*
* punctele sunt sortate dupa semnul componentei z din produsul incrucisat al vectorilor cu capete in puncte si originea in p[1]
* astfel, punctele de la inceput au putine (sau chiar 0) puncte a caror vector sa se afle in stanga lor
* iar punctele spre sfarsit au multe (chiar toate)
* altfel, punctele sunt sortate in functie de unghiul pe care il fac cu originea unui sistem de axe interschimbate (X interschimbat cu Y), avandu-l in centru pe p[1]
* adica unghiul creste din stanga spre dreapta, invers trigonometric
*/
stiva[1] = p[1];
stiva[2] = p[2];
varf = 2;
for(int i = 3; i <= n; i++){
while(varf >= 2 && produsIncrucisat(stiva[varf - 1], stiva[varf], p[i]) > 0) // > 0 <=> vectorul lui p[i] (cu originea in stiva[varf - 1] si capatul in p[i]) se afla in stanga celui lui stiva[varf]
varf--;
stiva[++varf] = p[i];
}
g << varf << '\n';
for(int i = varf; i >= 1; i--) // ordinea 1 ... varf este cea a acelor de ceasornic; noua ne trebuie ordinea trigonometrica
g << fixed << setprecision(9) << stiva[i].x << ' ' << stiva[i].y << '\n';
g.close();
}