Pagini recente » Cod sursa (job #955128) | Cod sursa (job #949508) | Cod sursa (job #725401) | Cod sursa (job #1448169) | Cod sursa (job #1976434)
#include<fstream>
#include<algorithm>
#include<iomanip>
#define x first
#define y second
#define DIM 120005
#define eps 0.0000000000001
using namespace std;
int n, i, u, j;
int s[DIM];
pair<double, double> v[DIM];
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
double det(pair<double, double> p1, pair<double, double> p2, pair<double, double> p3){
return (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
}
int cmp(pair<double, double> a, pair<double, double> b){
return det(v[1], a, b) > eps;
}
int main(){
fin>> n;
j = 0;
v[0] = make_pair(1000000000, 1000000000);
for(i = 1; i <= n; i++){
fin>> v[i].x >> v[i].y;
if(v[i].y < v[j].y){
j = i;
}
}
swap(v[1], v[j]);
sort(v + 2, v + n + 1, cmp);
s[1] = 1;
s[2] = 2;
u = 2;
for(i = 3; i <= n; i++){
while(u >= 2 && det(v[i], v[ s[u] ], v[ s[u - 1] ]) > eps){
u--;
}
s[++u] = i;
}
fout<< u <<"\n";
for(i = 1; i <= u; i++){
fout<< setprecision(6) << fixed << v[ s[i] ].x <<" ";
fout<< setprecision(6) << fixed << v[ s[i] ].y <<"\n";
}
return 0;
}