Pagini recente » Cod sursa (job #639451) | Cod sursa (job #1313988) | Cod sursa (job #2575394) | Cod sursa (job #1860392) | Cod sursa (job #2878118)
#include <bits/stdc++.h>
using namespace std;
struct Point {
long double x, y;
long double operator *(const Point&other) {
return x*other.y - other.x*y;
}
};
bool comp(Point a, Point b) {
if(a.x != b.x) return a.x < b.x;
return a.y < b.y;
}
bool crease(Point A, Point B, Point C) {
B.x -= A.x; B.y -= A.y;
C.x -= A.x; C.y -= A.y;
return (B*C) > 0;
}
int main() {
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n; f >> n;
vector<Point> v(n);
for(int i=0; i<n; i++)
f >> v[i].x >> v[i].y;
sort(v.begin(), v.end(), comp);
vector<Point> st;
for(int i=0; i<n; i++) {
while(st.size()>=2 and crease(st[st.size()-2], v[i], st[st.size()-1]))
st.pop_back();
st.push_back(v[i]);
}
for(int i=n-2; i>0; i--) {
while(st.size()>=2 and crease(st[st.size()-2], v[i], st[st.size()-1]))
st.pop_back();
st.push_back(v[i]);
}
g << st.size() << "\n";
for(auto i : st) g << fixed << setprecision(12) << i.x << " " << i.y << "\n";
return 0;
}