Pagini recente » Cod sursa (job #295435) | Cod sursa (job #532429) | Cod sursa (job #3311362) | Cod sursa (job #3334932) | Cod sursa (job #3323612)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct Vector2 {
long double x, y;
Vector2(long double x, long double y) {
this->x=x;
this->y=y;
}
Vector2();
Vector2 operator+(Vector2 vec) {
return Vector2(this->x+vec.x, this->y+vec.y);
}
Vector2 operator-(Vector2 vec) {
return Vector2(this->x-vec.x, this->y-vec.y);
}
long double operator*(Vector2 vec) {
return this->x*vec.y-this->y*vec.x;
}
static bool order(Vector2 a, Vector2 b, Vector2 c) {
return ((a-b)*(c-b))<=0;
}
};
bool cmp(const Vector2 &a, const Vector2 &b) {
if(a.x==b.x) return a.y<b.y;
return a.x < b.x;
}
vector<Vector2> hull;
vector<Vector2> a;
int n;
int main() {
Vector2 current(0, 0);
cin>>n;
for(int i=0;i<n;i++) {
cin>>current.x>>current.y;
a.push_back(current);
}
sort(a.begin(), a.end(), cmp);
for(int i=0;i<n;i++) {
while(hull.size()>=2 && Vector2::order(a[i], hull.back(), hull[hull.size()-2])) {
hull.pop_back();
}
hull.push_back(a[i]);
}
size_t lower_size=hull.size();
for(int i=n-1;i>0;i--) {
while(lower_size<hull.size() && hull.size()>=2 && Vector2::order(a[i], hull.back(), hull[hull.size()-2])) {
hull.pop_back();
}
hull.push_back(a[i]);
}
for(auto pos:hull) {
cout<<setprecision(6)<<fixed<<pos.x<<' '<<pos.y<<'\n';
}
return 0;
}