Pagini recente » Cod sursa (job #925414) | Cod sursa (job #1930320) | Cod sursa (job #1501568) | Diferente pentru autumn-warmup-2007/solutii/runda-2 intre reviziile 56 si 19 | Cod sursa (job #1852079)
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>
#define NMAX 120005
using namespace std;
typedef pair<double, double> pii;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
pii v[NMAX];
vector<pii> infasuratoare;
inline double unghi(pii a, pii b, pii c) {
return a.first*b.second+b.first*c.second+c.first*a.second -b.second*c.first-c.second*a.first-a.second*b.first;
}
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;
}