Pagini recente » Cod sursa (job #2071570) | Implica-te! | Istoria paginii runda/ichb-scoala-2014-11-12 | Arhiva de probleme | Cod sursa (job #2195540)
#include <iostream>
using namespace std;
#define point pair < double, double >
const int Nmax = 120000;
point a[Nmax];
int stk[Nmax];
int n, m;
void readData() {
freopen("infasuratoare.in" , "r" , stdin);
freopen("infasuratoare.out" , "w" , stdout);
scanf("%d", &n);
srand(time(0));
}
double getUnit() {
int Y = 1000000000;
int X = (1LL * rand() * rand()) % (Y + 1);
return 1.0 * X / Y;
}
double cross_product(point A, point B, point C) {
return (A.first - C.first) * (B.second - C.second) - (B.first - C.first) * (A.second - C.second);
}
bool compare(point A, point B) {
return cross_product(a[0] , A , B) > 0;
}
void readPoints() {
for (int i = 0 ; i < n ; ++i)
scanf("%lf%lf", &a[i].first, &a[i].second);
}
void generate() {
for (int i = 0 ; i < n; ++i) {
a[i].first = getUnit();
a[i].second = getUnit();
}
}
void graham() {
int j = 0;
for (int i = 0 ; i < n ; ++i) {
if (a[i] < a[j])
j = i;
}
swap(a[0], a[j]);
sort(a + 1, a + n, compare);
stk[++m] = 0;
stk[++m] = 1;
for (int i = 2 ; i < n ; ++i) {
while (m >= 2 && cross_product(a[stk[m]], a[stk[m-1]], a[i]) >= 0)
m--;
stk[++m] = i;
}
printf("%d\n", m);
for (int i = 1 ; i <= m ; ++i) {
printf("%.7lf %.7lf\n", a[stk[i]].first, a[stk[i]].second);
}
}
int main() {
readData();
//generate();
readPoints();
graham();
return 0;
}