Pagini recente » Cod sursa (job #2088194) | Cod sursa (job #990291) | Istoria paginii runda/vali_tigan/clasament | Cod sursa (job #1989622) | Cod sursa (job #1117497)
/// POO concepts
#include <fstream>
#include <iostream>
#include <vector>
#include <bitset>
#include <string.h>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <time.h>
#include <stdlib.h>
#include <set>
#include <map>
#include <string>
#include <queue>
#include <stack>
using namespace std;
const char infile[] = "infasuratoare.in";
const char outfile[] = "infasuratoare.out";
ifstream fin(infile);
ofstream fout(outfile);
const int MAXN = 100005;
const double oo = 0x3f3f3f3f;
typedef vector<int> Graph[MAXN];
typedef vector<int> :: iterator It;
const inline int min(const int &a, const int &b) { if( a > b ) return b; return a; }
const inline int max(const int &a, const int &b) { if( a < b ) return b; return a; }
const inline void Get_min(int &a, const int b) { if( a > b ) a = b; }
const inline void Get_max(int &a, const int b) { if( a < b ) a = b; }
#define x first
#define y second
#define T double
vector<pair<T, T> > Points;
pair<T, T> _Origin = make_pair(oo, oo);
int N, M;
int lowInd;
inline double crossPoint(const pair<T, T> &A, const pair<T, T> &B, const pair<T, T> &C) {
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
struct classComp {
inline bool operator () (const pair<T, T> &a, const pair<T, T> &b) const {
return crossPoint(_Origin, a, b) < 0;
}
};
inline void addPoint(pair<T, T> P) {
if(_Origin > P) {
_Origin = P;
lowInd = M;
}
Points.push_back(P);
++ M;
}
inline void sortPoint() {
swap(Points[0], Points[lowInd]);
sort(Points.begin() + 1, Points.end(), classComp());
}
inline stack < pair<T, T> > ConvexHull() {
stack < pair<T, T> > st;
vector < pair<T, T> > :: iterator it = Points.begin();
st.push(*it);
++ it;
st.push(*it);
for(++ it ; it != Points.end() ; ++ it) {
while(st.size() > 1) {
pair<T, T> p1 = st.top();
st.pop();
pair<T, T> p2 = st.top();
st.pop();
if(crossPoint(p2, p1, *it) > 0)
st.push(p2);
else {
st.push(p2);
st.push(p1);
break;
}
}
st.push(*it);
}
return st;
}
int main() {
fin >> N;
for(int i = 1 ; i <= N ; ++ i) {
pair<double, double> X;
fin >> X.x >> X.y;
addPoint(X);
}
sortPoint();
stack <pair<double, double > > convexHull = ConvexHull();
fout << convexHull.size() << fixed << setprecision(6) << '\n';
while(!convexHull.empty()) {
fout << convexHull.top().first << ' ' << convexHull.top().second << '\n';
convexHull.pop();
}
fin.close();
fout.close();
return 0;
}