Pagini recente » Cod sursa (job #2028798) | Cod sursa (job #1806491) | Cod sursa (job #488729) | Cod sursa (job #788809) | Cod sursa (job #1644234)
# include <cstdio>
# include <vector>
# include <algorithm>
# define pb push_back
# define po pop_back
# define pc pair<double, double>
# define x first
# define y second
using namespace std;
FILE *fin = fopen("infasuratoare.in", "rt");
FILE *fout = fopen("infasuratoare.out", "wt");
int n, k;
pc mn;
vector<pc> v, s;
bool comp(pc a, pc b) {
return ((a.y-mn.y)*(b.x-mn.x) < (b.y-mn.y)*(a.x-mn.x));
}
bool semn(pc a, pc b, pc c) {
return (((b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x)) <= 0);
}
int main() {
if (fscanf(fin, "%d", &n)) ;
pc A;
mn.x = mn.y = 1e9;
for (int i=0; i<n; ++i) {
if (fscanf(fin, "%lf%lf", &A.x, &A.y)) ;
if ((mn.y > A.y) || ((mn.y == A.y) && (mn.x > A.x))) {
mn = A;
k = i;
}
v.pb(A);
}
swap(v[k], v.back());
v.po();
sort(v.begin(), v.end(), comp);
s.pb(mn);
s.pb(v[0]);
s.pb(v[1]);
for (unsigned i=2; i<v.size(); ++i) {
while (semn(s[s.size()-2], s[s.size()-1], v[i]))
s.po();
s.pb(v[i]);
}
fprintf(fout, "%d\n", s.size()) ;
for (unsigned i=0; i<s.size(); ++i)
fprintf(fout, "%lf %lf\n", s[i].x, s[i].y);
return 0;
}