Pagini recente » Voteaza Algorel | Cod sursa (job #473656) | Cod sursa (job #1715025) | Cod sursa (job #2037533) | Cod sursa (job #1999837)
#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< long long, long long > a, pair< long long, long long > b, pair< long long, long long > c) {
long long 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, false);
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){
used[s.top()] =false;
s.pop();
}
used[i] = true;
s.push(i);
}
}
for(int i = 1; i <= n; i ++)
if(used[i])
cout << v[i].first << ' ' << v[i].second << '\n';
vector< bool > used2(n + 1);
stack< int > s2;
s2.push(n);
s2.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[s2.top()],v[i]) == -1){
s2.push(i);
used2[i] = true;
}
else {
while(get_sign_of_det(v[n],v[s2.top()],v[i]) != -1){
used2[s2.top()] =false;
s2.pop();
}
used2[i] = true;
s2.push(i);
}
}
for(int i = n; i >= 1; i --)
if(used2[i] and !used[i])
cout << v[i].first << ' ' << v[i].second << '\n';
}