Pagini recente » Cod sursa (job #2861034) | Cod sursa (job #698429) | Cod sursa (job #3150950) | Cod sursa (job #2350366) | Cod sursa (job #1211104)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define DIM 120010
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
vector< pair<double, double> > V;
int S[DIM];
int n, i, k, pminim;
double x, y;
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) -
(b.second-a.second) * (c.first-a.first);
}
int cmp(const pair<double, double> &a, const pair<double, double> &b) {
return det(V[0], a, b) >= 0;
}
int main() {
fin>>n;
for (i=1;i<=n;i++) {
fin>>x>>y;
V.push_back(make_pair(x, y));
}
pminim = 0;
for (i=1;i<V.size();i++)
if (V[i]< V[pminim])
pminim = i;
pair<double, double> aux = V[pminim];
V[pminim] = V[0];
V[0] = aux;
for (i=0;i<V.size(); i++) {
V[i].first -= aux.first;
V[i].second -= aux.second;
}
sort(V.begin()+1, V.end(), cmp);
/*
for (i=0;i<n;i++)
fout<<V[i].first<<" "<<V[i].second<<"\n";
*/
S[1] = 0;
S[2] = 1;
k = 2;
for (i=2;i<V.size(); i++) {
while (k >= 2 && det(V[ S[k-1] ], V[ S[k] ], V[i])<=0)
k--;
S[++k] = i;
}
fout<<k<<"\n";
fout<<fixed;
for (i=1;i<=k;i++)
fout<<setprecision(9) <<V[ S[i] ].first + aux.first<<" "<<V[ S[i] ].second + aux.second<<"\n";
return 0;
}