Pagini recente » Cod sursa (job #47935) | Cod sursa (job #1021422) | Cod sursa (job #2499628) | Cod sursa (job #241081) | Cod sursa (job #1999910)
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
double get_sign_of_det(pair< double, double > a, pair< double, double > b, pair< double, double > c) {
double det = (a.first * b.second) + (b.first * c.second) + (c.first * a.second) - (a.second * b.first) - (b.second * c.first) - (c.second * a.first);
if(det == 0)
return 0;
if(det > 0)
return 1;
return -1;
}
int main() {
cout << fixed << setprecision(6);
int n;
cin >> n;
vector< pair< double, double > > v(n + 1);
vector< bool > used(n + 1);
for(int i = 1; i <= n; i ++) {
double x, y;
cin >> x >> y;
v[i] = make_pair(x, y);
}
sort(v.begin() + 1, v.end());
stack< int > s;
s.push(1);
s.push(2);
used[1] = true;
used[2] = true;
for(int i = 3; i <= n; i ++) {
if(get_sign_of_det(v[1],v[s.top()],v[i]) > 1){
s.push(i);
used[i] = true;
}
else {
while(get_sign_of_det(v[1],v[s.top()],v[i]) != -1 and s.size() > 1){
used[s.top()] =false;
s.pop();
}
used[i] = true;
s.push(i);
}
}
vector< bool > used2(n + 1);
int min_size = s.size() + 1;
s.push(n);
s.push(n - 1);
used2[n] = true;
used2[n - 1] = true;
for(int i = n - 2; i >= 1; i --) {
if(get_sign_of_det(v[n],v[s.top()],v[i]) > 1){
s.push(i);
used2[i] = true;
}
else {
while(get_sign_of_det(v[n],v[s.top()],v[i]) != -1 and s.size() > min_size){
used2[s.top()] =false;
s.pop();
}
used2[i] = true;
s.push(i);
}
}
int sol = 0;
for(int i = 1; i <= n; i++)
if(used[i] or used2[i]){
sol ++;
used[i] = true;
}
cout << sol << '\n';
while(!s.empty()) {
if(used[s.top()]){
cout << v[s.top()].first << ' ' << v[s.top()].second << '\n';
used[s.top()] = false;
}
s.pop();
}
}