Pagini recente » Cod sursa (job #1793722) | Cod sursa (job #2956365) | Cod sursa (job #834473) | Cod sursa (job #1002514) | Cod sursa (job #1545899)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <stack>
#define MAXN 120000
using namespace std;
struct point{
double x, y;
};
point pivot;
point v[MAXN + 1];
point sol[MAXN + 1];
point zero;
point S[MAXN + 1];
inline double dist(point A, point B) {
return ((A.x - B.x) * (A.x - B.x)) + ((A.y - B.y) * (A.y - B.y));
}
inline double E(point A, point B, point C) {
double k = ((B.x - A.x) * (C.y - A.y)) - ((C.x - A.x) * (B.y - A.y));
return k;
}
inline bool cmp(point A, point B) {
double x = E(pivot, A, B);
// if (x == 0)
// return (dist(pivot, A) < dist(pivot, B));
return (x < 0);
}
inline bool trigo(point A, point B) {
double x = E(A, B, zero);
return (x > 0);
}
int main () {
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int n;
cin >> n;
pivot.y = 1000000000;
pivot.x = 1000000000;
for (int i = 0 ; i < n ; ++i) {
cin >> v[i].x >> v[i].y;
if (v[i].y < pivot.y || (v[i].y == pivot.y && v[i].x < pivot.x))
pivot = v[i];
}
sort(v, v + n, cmp);
S[0] = v[0];
int ps = 0;
for (int i = 1 ; i < n ; ++i) {
while (ps > 0 && E(S[ps - 1], S[ps], v[i]) > 0)
--ps;
++ps;
S[ps] = v[i];
}
++ps;
// sort(S, S + ps, trigo);
cout << ps << "\n";
for (int i = ps - 1 ; i >= 0 ; --i)
cout << S[i].x << " " << S[i].y << "\n";
return 0;
}