Pagini recente » Cod sursa (job #678613) | Cod sursa (job #2152332) | Cod sursa (job #2978134) | Cod sursa (job #1180281) | Cod sursa (job #2439334)
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
typedef pair<double, double> Point;
const int NMAX = 120005;
const int inf = 1000000006;
int n, head;
Point Stack[NMAX], v[NMAX];
double cross_product(const Point &X, const Point &Y, const Point &Z){
return (Y.first - X.first) * (Z.second - X.second) - (Y.second - X.second) * (Z.first - X.first);
}
bool cmp(const Point &X, const Point &Y){
return cross_product(v[1], X, Y) < 0;
}
void sort_points(){
int pos = 1,i;
for(i = 2 ; i <= n ; i++)
if(v[i] < v[pos])
pos = i;
swap(v[1], v[pos]);
sort(v + 2, v + n + 1, cmp);
}
int main(){
int i;
f >> n;
for(i = 1 ; i <= n ; i++)
f >> v[i].first >> v[i].second;
sort_points();
Stack[1] = v[1];
Stack[2] = v[2];
head = 2;
for(i = 3 ; i <= n; i++){
while(head >= 2 && cross_product(Stack[head - 1], Stack [head], v[i]) > 0)
head--;
Stack[++head] = v[i];
}
g << head << "\n";
for(i = head ; i >= 1 ; i--)
g << fixed << setprecision(6) << Stack[i].first << " " << Stack[i].second << "\n";
return 0;
}