Pagini recente » Cod sursa (job #1339233) | Cod sursa (job #1357921) | Cod sursa (job #2797874) | Cod sursa (job #23913) | Cod sursa (job #2511152)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 12*1e4 + 50;
const int INF = 1e8;
const long double EPS = 1e-12;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct{
long double x, y, panta;
}p[MAXN];
bool cmp(punct a, punct b){
return a.panta + EPS < b.panta || (a.panta == b.panta && a.x + EPS< b.x);
}
bool trig(punct a, punct b, punct c){
return (a.x - c. x) * (b.y - c.y) - (a.y - c.y) * (b.x - c.x) < 0 ;
}
int main()
{
ios::sync_with_stdio(false);
fin.tie(0); fout.tie(0);
int n, indice = 1; fin >> n;
for(int i = 1; i <= n; ++i){
fin >> p[i].x >> p[i].y;
if(p[i].x < p[indice].x || (p[i].x == p[indice].x && p[i].y <= p[indice].y))
indice = i;
}
swap(p[1], p[indice]);
for(int i = 2; i <= n; ++i){
if(p[i].x == p[indice].x) p[i].panta = INF;
else p[i].panta = (p[i].y - p[indice].y) / (p[i].x - p[indice].x);
}
sort(p + 2, p + n + 1, cmp);
p[n + 1] = p[1];
deque <int> stiva ;
int i = 3;
stiva.push_back(1);
stiva.push_back(2);
while(i <= n + 1 and stiva.back() != stiva.front()){
if(stiva.size() <= 1) stiva.push_back(i);
else
while(stiva.size() >= 2 and trig(p[stiva[stiva.size()- 2]], p[stiva[stiva.size() - 1]], p[i]))
stiva.pop_back();
stiva.push_back(i);
++i;
}
fout << stiva.size() - 1<< '\n';
for(int i = 1; i <= (int)stiva.size() - 1 ; ++i)
fout << setprecision(7) << fixed << p[stiva[i]].x << " " << p[stiva[i]].y << '\n';
return 0;
}