Pagini recente » Cod sursa (job #595896) | Cod sursa (job #1364590) | Cod sursa (job #1528892) | Cod sursa (job #341214) | Cod sursa (job #1258368)
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>
using namespace std;
typedef pair<double, double> Point;
double cross(const Point &p0, const Point &a,const Point &b) {
double x1 = a.first - p0.first, y1 = a.second - p0.second,
x2 = b.first - p0.first, y2 = b.second - p0.second;
return x1 * y2 - x2 * y1;
}
struct cmp {
Point p0;
cmp(Point &p0) : p0(p0) {}
bool operator() (const Point& a, const Point &b) {
return cross(p0, a, b) > 0;
}
};
int main() {
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n;
f>>n;
vector<Point> P(n, Point());
for(int i = 0; i < n;i ++) {
f >> P[i].first >> P[i].second;
}
int min = 0;
for(int i = 1; i < n; i++) {
if(P[min] > P[i])
min = i;
}
Point tmp = P[min];
P[min] = P[0];
P[0] = tmp;
sort( P.begin() + 1, P.end() , cmp(P[0]));
vector<int> S;
S.push_back(0);
S.push_back(1);
for(int i = 2; i < n; i++) {
while(S.size() > 1 && cross(P[S[S.size() - 2]], P[S[S.size() - 1]], P[i] ) < 0) {
S.pop_back();
}
if(S.size() == 1 || cross(P[S[S.size() - 2]], P[S[S.size() - 1]], P[i] ) > 0)
S.push_back(i);
}
g << S.size() << endl;
g << setprecision(6) << fixed;
for(int i = 0; i < S.size(); i++) {
g << P[S[i]].first << ' ' << P[S[i]].second << endl;
}
return 0;
}