Pagini recente » Cod sursa (job #530218) | Cod sursa (job #1469879) | Cod sursa (job #1031153) | Cod sursa (job #2903072) | Cod sursa (job #2410146)
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ld, ld> pld;
const string file = "infasuratoare";
const ll INF = 9223372036854775807ll;
const int inf = 2147483647, nmax = 120005;
int n, vf;
pld v[nmax], first = {inf, inf}, s[nmax];
bool rightturn(pld a, pld b, pld c)
{
ld sum = 0;
sum += a.ff*b.ss;
sum += b.ff*c.ss;
sum += c.ff*a.ss;
sum -= c.ff*b.ss;
sum -= b.ff*a.ss;
sum -= a.ff*c.ss;
return sum < 0;
}
bool cmp(pld a, pld b)
{
return (a.ss-first.ss)*(b.ff-first.ff) > (b.ss-first.ss)*(a.ff-first.ff);
}
int main()
{
ifstream fin (file+".in");
ofstream fout (file+".out");
fin >> n;
for (int i = 1; i <= n; ++i){
fin >> v[i].ff >> v[i].ss;
first = min(first, v[i]);
}
for (int i = 1; i <= n; ++i)
if(v[i] == first){
for (int j = i; j < n; ++j)
v[j] = v[j+1];
--n;
break;
}
sort(v+1, v+n+1, cmp);
s[++vf] = first;
s[++vf] = v[1];
for (int i = 2; i <= n; ++i){
while(vf >= 2 && !rightturn(s[vf-1], s[vf], v[i]))
--vf;
s[++vf] = v[i];
}
fout << vf << "\n";
for (int i = vf; i >= 1; --i)
fout << fixed << setprecision(10) << s[i].ff << " " << s[i].ss << "\n";
return 0;
}