Pagini recente » Cod sursa (job #2286106) | Cod sursa (job #1584875) | Cod sursa (job #1912675) | Cod sursa (job #1625859) | Cod sursa (job #2211526)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
int i, n, s = 1, k = 2;
struct point{
double x, y;
}p[120010], ans[120010];
bool det(point a, point b, point c){
return (a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - c.y * a.x - a.y * b.x > 0);
}
bool cmp(point a, point b){
return det(p[1], a, b);
}
int main(){
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
cin >> n;
for(i = 1; i <= n; i++){
cin >> p[i].x >> p[i].y;
if(p[i].x < p[s].x || (p[i].x == p[s].x && p[i].y < p[s].y))
s = i;
}
swap(p[1], p[s]);
sort(p + 2, p + n + 1, cmp);
ans[1] = p[1];
ans[2] = p[2];
for(i = 3; i <= n; i++){
while(!det(ans[k - 1], ans[k], p[i]))
k--;
ans[++k] = p[i];
}
cout << k << "\n" << fixed << setprecision(12);
for(i = 1; i <= k; i++)
cout << ans[i].x << " " << ans[i].y << "\n";
return 0;
}