Pagini recente » Cod sursa (job #2206509) | Cod sursa (job #473168) | Cod sursa (job #2058272) | Cod sursa (job #473174) | Cod sursa (job #2564313)
#include <bits/stdc++.h>
using namespace std;
#define zero(x) (x & (-x))
#define ll long long
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int MAXN = 120000 + 3;
const double EPS = 1e-12;
const long double INF = 1e8;
struct punct{
long double x, y, panta;
}v[MAXN];
int indice = 1;
bool operatie(punct a, punct b, punct c){
return (a.x - c.x) * (b.y - c.y) - (a.y - c.y) * (b.x - c.x) >= 0;
}
bool cmp(punct a, punct b){
return a.panta < b.panta;
}
int main(){
int n; fin >> n;
for(int i = 1; i <= n; ++i){
fin >> v[i].x >> v[i].y;
if(v[i].x < v[indice].x || (v[i].x == v[indice].x and v[i].y < v[indice].y))
indice = i;
}
swap(v[1], v[indice]);
for(int i = 2; i <= n; ++i){
if(v[i].x == v[1].x) v[i].panta = INF;
else v[i].panta = (v[i].y - v[1].y) / (v[i].x - v[1].x);
}
sort(v + 2, v + n + 1, cmp);
v[n + 1] = v[1];
deque <int> stiva;
int i = 3;
stiva.push_back(1);
stiva.push_back(2);
while(i <= n + 1 and stiva.back() != stiva.front()){
while(stiva.size() >= 2 and !operatie(v[stiva[stiva.size()- 2]], v[stiva[stiva.size()- 1]], v[i]))
stiva.pop_back();
stiva.push_back(i++);
}
fout << stiva.size() - 1 << '\n' ;
for(int i = 0; i <= stiva.size() - 2; ++i)
fout << setprecision(6) << fixed << v[stiva[i]].x << " " << v[stiva[i]].y << '\n';
return 0;
}