Pagini recente » Cod sursa (job #1556274) | Cod sursa (job #2894884) | Cod sursa (job #2039476) | Cod sursa (job #144811) | Cod sursa (job #1148972)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N;
double x, y;
vector<pair<double, double> > v, stack;
pair<double, double> minim;
void read(){
scanf("%d", &N);
scanf("%lf %lf", &x, &y);
minim = make_pair(x,y);
for (int i=1; i<N; ++i){
pair<double, double> point;
scanf("%lf %lf", &x, &y);
point = make_pair(x, y);
if (minim < point){
v.push_back(point);
}
else{
v.push_back(minim);
minim = point;
}
}
}
bool comp(pair<double, double> first, pair<double, double> second){
return minim.first*first.second+first.first*second.second+second.first*minim.second-
second.first*first.second-first.first*minim.second-minim.first*second.second > 0;
}
bool trig_ord(pair<double, double> p1, pair<double, double> p2, pair<double, double> p3){
return p1.first*p2.second+p2.first*p3.second+p3.first*p1.second-
p3.first*p2.second-p2.first*p1.second-p1.first*p3.second > 0;
}
void solve(){
stack.push_back(minim);
stack.push_back(v[0]);
for (unsigned i=1; i<v.size();){
if (trig_ord(stack[stack.size()-2], stack[stack.size()-1], v[i])){
stack.push_back(v[i]);
++i;
}
else{
stack.pop_back();
}
}
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
read();
sort(v.begin(), v.end(), comp);
v.push_back(minim);
solve();
printf("%d\n", stack.size()-1);
for (int i=0, l=stack.size()-1; i<l; ++i){
printf("%lf %lf\n", stack[i].first, stack[i].second);
}
return 0;
}