Pagini recente » Cod sursa (job #2024255) | Cod sursa (job #1596591) | Cod sursa (job #104766) | Monitorul de evaluare | Cod sursa (job #916464)
Cod sursa(job #916464)
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;
const int N = 120005;
const double E = 1e-12;
struct Point{
double x, y;
Point(){
x = y = 0;
}
Point(double _x, double _y){
x = _x;
y = _y;
}
inline Point operator-(Point P){
return Point(x - P.x, y - P.y);
}
inline bool operator<(const Point& P) const {
return x < P.x || (x == P.x && y < P.y);
}
};
class ConvexHull{
inline bool bad(Point A, Point B){
return A.x * B.y - A.y * B.x < E;
}
inline bool bad(Point A, Point B, Point C){
return bad(B - A, C - A);
}
void compute(vector<Point>& v, vector<int>& index, bool use[], int x){
if (use[x])
return;
while (index.size() > 1 && bad( v[ index[ index.size() - 2 ] ], v[ index.back() ], v[x] )){
use[index.back()] = false;
index.pop_back();
}
index.push_back(x);
use[x] = true;
}
public:
void convexHull(vector<Point>& v){
vector<int> index;
bool use[v.size()];
sort(v.begin(), v.end());
memset(use, false, sizeof(use));
for (size_t i = 0 ; i < v.size() ; i++)
compute(v, index, use, i);
use[0] = false;
for (size_t i = v.size() - 1 ; i ; i--)
compute(v, index, use, i);
index.pop_back();
vector<Point> ans;
ans.reserve(index.size());
for (vector<int> :: iterator it = index.begin() ; it != index.end() ; it++)
ans.push_back(v[*it]);
v.swap(ans);
}
};
ConvexHull H;
vector<Point> v;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int main(){
int n;
double x, y;
in >> n;
v.reserve(n);
while(n--){
in >> x >> y;
v.push_back(Point(x, y));
}
H.convexHull(v);
out << v.size() << "\n";
for (vector<Point> :: iterator it = v.begin() ; it != v.end() ; it++)
out << (it -> x) << " " << (it -> y) << "\n";
return 0;
}