Pagini recente » Cod sursa (job #1934106) | Cod sursa (job #1375759) | Cod sursa (job #3192862) | Cod sursa (job #1046120) | Cod sursa (job #1584404)
#include <iostream>
#include <fstream>
#include <stack>
#include <cmath>
#include <vector>
#include <algorithm>
#include <iomanip>
#define inf 1000000000
using namespace std;
pair<double, double> O;
double orient(pair<double, double> a, pair<double, double> b, pair<double, double> c){
double x, y;
x = (b.first - a.first) * (c.second - a.second);
y = (b.second - a.second) * (c.first - a.first);
return x-y;
}
bool cmp1(pair<double, double> a, pair<double, double> b){
return (orient(O, a, b) > 0);
}
int main(){
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n;
vector<pair<double, double> > V;
O = make_pair(inf, inf);
f >> n;
int it = 0;
for (int i = 0; i < n; ++i){
double x, y;
f >> x >> y;
pair<double, double> P(x, y);
V.push_back(P);
if (O.first == P.first){
if (O.second > P.second){
O = P;
it = i;
}
}
else
if (O.first > P.first){
O = P;
it = i;
}
}
swap(V[0],V[it]);
sort(V.begin()+1, V.end(), cmp1);
vector<pair<double, double> > S;
S.push_back(V[0]);
S.push_back(V[1]);
for (int i = 2; i < V.size(); ++i){
while (S.size() >= 2 && orient(S[S.size() - 2], S[S.size() - 1], V[i]) <= 0)
S.pop_back();
S.push_back(V[i]);
}
g << fixed << setprecision(12) << S.size() << "\n";
for (int i = 0; i <= S.size() - 1; ++i)
g << S[i].first << " " << S[i].second << "\n";
f.close();
g.close();
return 0;
}