Pagini recente » Cod sursa (job #3304279) | Cod sursa (job #2295631) | Cod sursa (job #2239041) | Cod sursa (job #2063057) | Cod sursa (job #3338230)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int NMAX=12e4+1;
int n;
pair <double, double> v[NMAX];
vector <int> sus, jos;
vector <pair <double, double>> rez;
double aria(pair <double, double> x, pair <double, double> y, pair <double, double> z){
return x.first * (y.second - z.second) + y.first * (z.second - x.second) + z.first * (x.second - y.second);
}
int main(){
fin>>n;
for(int i=1;i<=n;i++)
fin>>v[i].first>>v[i].second;
sort(v+1, v+1+n);
for(int i=1;i<=n;i++){
while(jos.size()>1&&aria(v[jos[jos.size()-2]], v[jos[jos.size()-1]], v[i])<=0)
jos.pop_back();
while(sus.size()>1&&aria(v[sus[sus.size()-2]], v[sus[sus.size()-1]], v[i])>=0)
sus.pop_back();
jos.push_back(i);
sus.push_back(i);
}
for(int a:jos)
rez.push_back(v[a]);
sus.pop_back();
reverse(sus.begin(), sus.end());
sus.pop_back();
for(int a:sus)
rez.push_back(v[a]);
fout<<rez.size()<<'\n';
fout<<fixed<<setprecision(6);
for(auto a:rez){
fout<<a.first<<' '<<a.second<<'\n';
}
return 0;
}