Pagini recente » Cod sursa (job #852564) | Cod sursa (job #3124784) | Cod sursa (job #1742632) | Cod sursa (job #2034966) | Cod sursa (job #1999979)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define MAX 25e4
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
class StaculetzMagic {
public:
StaculetzMagic() {
this -> sz = 0;
staculetz.resize(MAX);
}
int size(){
return this -> sz;
}
bool empty(){
return sz == 0;
}
void pop() {
sz --;
}
void push(int n) {
staculetz[++ sz] = n;
}
int sec() {
return staculetz[sz - 1];
}
int top(){
return staculetz[sz];
}
vector< int > staculetz;
private:
int sz;
};
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);
StaculetzMagic *s = new StaculetzMagic();
int n;
cin >> n;
vector< pair< double, double > > v(n + 1);
vector< bool > used(n + 1);
for(int i = 1; i <= n; i ++) {
cin >> v[i].first >> v[i].second;
}
sort(v.begin() + 1, v.end());
int sol = 1;
s -> push(1);
s -> push(2);
used[2] = true;
for(int i = 3; i <= n; i ++) {
while(get_sign_of_det(v[s -> sec()], v[s -> top()], v[i]) != -1 and s -> size() > 1) {
used[s -> top()] = false;
s -> pop();
sol --;
}
s -> push(i);
used[i] = true;
sol ++;
}
int min_size = s -> size();
for(int i = n - 1; i >= 1; i --) {
if(used[i])
continue;
while(get_sign_of_det(v[s -> sec()], v[s -> top()], v[i]) != -1 and s -> size() > min_size) {
used[s -> top()] = false;
s -> pop();
sol --;
}
s -> push(i);
used[i] = true;
sol ++;
}
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();
}
delete s;
}