Pagini recente » Cod sursa (job #1059191) | Cod sursa (job #728094) | Cod sursa (job #2941217) | Cod sursa (job #2267552) | Cod sursa (job #1584382)
#include <iostream>
#include <fstream>
#include <stack>
#include <cmath>
#include <vector>
#include <algorithm>
#include <iomanip>
#define eps 0.000000000000001
#define inf 1000000000
using namespace std;
pair<double, double> O;
bool 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 > 0;
}
bool cmp1(pair<double, double> a, pair<double, double> b){
double x, y;
x = atan2(a.second - O.second, a.first - O.first);
y = atan2(b.second - O.second, b.first - O.first);
return x < y;
}
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);
stack<pair<double, double> > S;
S.push(V[0]);
for (int i = 1; i < V.size() - 1; ++i){
if (orient(S.top(), V[i], V[i + 1]))
S.push(V[i]);
}
if (orient(S.top(), V[V.size() - 1], O))
S.push(V[V.size() - 1]);
g << fixed << setprecision(12) << S.size() << "\n";
while (!S.empty()){
g << S.top().first << " " << S.top().second << "\n";
S.pop();
}
f.close();
g.close();
return 0;
}