Pagini recente » Cod sursa (job #2109263) | Cod sursa (job #516768) | Cod sursa (job #1601433) | Cod sursa (job #2232156) | Cod sursa (job #916414)
Cod sursa(job #916414)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
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 < 0;
}
inline bool bad(Point A, Point B, Point C){
return bad(B - A, C - A);
}
public:
void convexHull(vector<Point>& v){
vector<Point> ans;
sort(v.begin(), v.end());
for (size_t i = 0 ; i < v.size() ; i++){
while (ans.size() > 1 && bad(ans[ ans.size() - 2 ], ans.back(), v[i]))
ans.pop_back();
ans.push_back(v[i]);
}
for (size_t i = v.size() - 2 ; i ; i--){
while (ans.size() > 1 && bad(ans[ ans.size() - 2 ], ans.back(), v[i]))
ans.pop_back();
ans.push_back(v[i]);
}
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;
}