Pagini recente » Cod sursa (job #2471203) | Cod sursa (job #909113) | Cod sursa (job #576363) | Cod sursa (job #1376452) | Cod sursa (job #3214457)
#include <fstream>
#include <algorithm>
#include <iomanip>
#define DIM 120010
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
pair<double, double> v[DIM], s[DIM], aux;
int n, k, i, p;
double det(const pair<double, double> &a, const pair<double, double> &b, const pair<double, double> &c) {
return (b.first-a.first)*(c.second-a.second) - (c.first-a.first)*(b.second-a.second);
}
int cmp( const pair<double, double> &a, const pair<double, double> &b ) {
return det(v[1], a, b) > 0;
}
int main() {
fin>>n;
for (i=1;i<=n;i++)
fin>>v[i].first>>v[i].second;
p = 1;
for (i=2;i<=n;i++)
if (v[i] < v[p])
p = i;
aux = v[1];
v[1] = v[p];
v[p] = aux;
sort(v+2, v+n+1, cmp);
s[1] = v[1];
s[2] = v[2];
k = 2;
for (i=3;i<=n;i++) {
while (k >= 2 && det(s[k-1], s[k], v[i]) <= 0 ) {
k--;
}
s[++k] = v[i];
}
fout<<k<<"\n";
for (i=1;i<=k;i++)
fout<<setprecision(9)<<fixed<<s[i].first<<" "<<s[i].second<<"\n";
return 0;
}