Pagini recente » Cod sursa (job #494887) | Cod sursa (job #2485099) | Cod sursa (job #802989) | Cod sursa (job #374262) | Cod sursa (job #1853178)
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>
#define NMAX 120005
using namespace std;
typedef pair<long double, long double> pii;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
pii v[NMAX];
vector<pii> infasuratoare;
inline long double unghi(pii a, pii b, pii c) {
long double x=a.first*b.second+b.first*c.second+c.first*a.second,y=b.second*c.first+c.second*a.first+a.second*b.first;
return x-y;
}
int main() {
int n,i;
fin>>n;
for(i=1;i<=n;++i) fin>>v[i].first>>v[i].second;
sort(v+1,v+n+1);
infasuratoare.push_back(v[1]);
infasuratoare.push_back(v[2]);
for(i=3;i<=n;++i) {
while(infasuratoare.size()>1 && unghi(infasuratoare[infasuratoare.size()-2],infasuratoare.back(),v[i])<0)
infasuratoare.pop_back();
infasuratoare.push_back(v[i]);
}
for(i=n-1;i>0;--i) {
while(infasuratoare.size()>1 && unghi(infasuratoare[infasuratoare.size()-2],infasuratoare.back(),v[i])<0)
infasuratoare.pop_back();
infasuratoare.push_back(v[i]);
}
infasuratoare.pop_back();
fout<<infasuratoare.size()<<'\n';
for(auto it:infasuratoare)
fout<<fixed<<setprecision(12)<<it.first<<' '<<it.second<<'\n';
return 0;
}