Pagini recente » Cod sursa (job #2933051) | Cod sursa (job #3356921) | Cod sursa (job #2366656) | Cod sursa (job #2889052) | Cod sursa (job #3318712)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
struct pct{
long double x, y;
} V[120005];
long double D(pct a, pct b, pct c){
return (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);
}
bool cmp(pct a, pct b){
if (a.x != b.x) return a.x < b.x;
return a.y < b.y;
}
void citire(){
fin>>n;
for (int i = 0; i < n; i++)
fin>>V[i].x>>V[i].y;
}
int main()
{
citire();
sort(V, V + n, cmp);
vector<pct> S;
for (int i = 0; i < n; i++) {
while (S.size() >= 2 && D(S[S.size()-2], S.back(), V[i]) <= 0)
S.pop_back();
S.push_back(V[i]);
}
int t = S.size() + 1;
for (int i = n - 2; i >= 0; i--) {
while (S.size() >= t && D(S[S.size()-2], S.back(), V[i]) <= 0)
S.pop_back();
S.push_back(V[i]);
}
S.pop_back();
fout<<S.size()<<"\n"<<fixed<<setprecision(6);
for (auto &p : S)
fout<<p.x<<" "<<p.y<<"\n";
}