Pagini recente » Cod sursa (job #2698472) | Cod sursa (job #1445332) | Cod sursa (job #2575410) | Cod sursa (job #3222426) | Cod sursa (job #2189260)
#include <bits/stdc++.h>
#define ld long double
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Point{
ld x;
ld y;
};
Point p[120010];
Point st[120010];
Point mini;
int n;
int k;
int pos;
ld area(Point a, Point b, Point c){
return (ld)1/2 * (a.x * b.y + b.x * c.y + c.x * a.y - b.y * c.x - c.y * a.x - a.y * b.x);
}
bool comp(Point a, Point b){
/*if(a.x == mini.x && a.y == mini.y) return 0;
if(b.x == mini.x && b.y == mini.y) return 1;*/
if(area(mini, a, b) > 0) return 1;
return 0;
}
int main()
{
fin >> n;
mini.x = 1000000010;
mini.y = 1000000010;
for(int i = 0; i < n; i++){
fin >> p[i].x >> p[i].y;
if(p[i].x < mini.x) mini.x = p[i].x, mini.y = p[i].y, pos = i;
else if(p[i].x == mini.x && p[i].y < mini.y) mini.y = p[i].y, pos = i;
}
swap(p[0], p[pos]);
sort(p + 1, p + n, comp);
p[n] = mini;
st[++k] = mini;
st[++k] = p[1];
for(int i = 2; i <= n; i++){
if(area(st[k - 1], st[k], p[i]) > 0) st[++k] = p[i];
else{
while(area(st[k - 1], st[k], p[i]) < 0 && k > 1) k--;
st[++k] = p[i];
}
}
fout << k - 1 << '\n';
fout << setprecision(12) << fixed;
for(int i = 1; i <= k - 1; i++){
fout << st[i].x << ' ' << st[i].y << '\n';
}
return 0;
}