Pagini recente » Cod sursa (job #46922) | Cod sursa (job #2888160) | Cod sursa (job #2124070) | Cod sursa (job #344338) | Cod sursa (job #2656524)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define e 1e-12
vector<pair<float, float>> points;
double crossProduct(pair<float, float> & a, pair<float, float> &b, pair<float, float> & c) {
return (b.first - a.first) * (c.second - a.second) - (b.second - a.second) * (c.first - a.first);
}
int comp(pair<float, float> a, pair<float, float> b) {
return crossProduct(points[0], a, b) < 0;
}
int main() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int n, minIndex = 0;
float x, y, aux;
scanf("%d", &n);
points.resize(n);
for (int i=0; i<n; ++i) {
scanf("%f%f", &x, &y);
points[i].first = x;
points[i].second = y;
if (x - points[minIndex].first < e && x - points[minIndex].first > -e && y < points[minIndex].second)
minIndex = i;
else
if (x < points[minIndex].first)
minIndex = i;
}
if (minIndex != 0) {
aux = points[minIndex].first;
points[minIndex].first = points[0].first;
points[0].first = aux;
aux = points[minIndex].second;
points[minIndex].second = points[0].second;
points[0].second = aux;
}
sort(points.begin() + 1, points.end(), comp);
vector<int> st;
st.push_back(0);
st.push_back(1);
for(int i=2; i<n; ++i) {
while(st.size() >= 2 && crossProduct(points[st[st.size() - 2]], points[st[st.size() - 1]], points[i]) > 0) {
st.pop_back();
}
st.push_back(i);
}
printf("%d\n", st.size());
for(int i=st.size() -1 ; i>=0; --i)
printf("%6f %6f\n", points[st[i]].first, points[st[i]].second);
return 0;
}