Pagini recente » Cod sursa (job #295439) | Cod sursa (job #3332906) | Cod sursa (job #542480) | Cod sursa (job #3324560) | Cod sursa (job #3317209)
#include <bits/stdc++.h>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
#define f first
#define s second
const int MXN = 120000;
const int BRD = 1e9;
int st[MXN + 1];
int vf, vfc;
struct punct {
double f, s;
int ord;
};
punct v[MXN + 1];
bool cmp(punct A, punct B) {
if(A.f != B.f)
return A.f < B.f;
else
return A.s < B.s;
}
bool peste(punct A, punct B, punct C) {
// "+" -> peste
// "-" -> sub
return (A.f * B.s + B.f * C.s + C.f * A.s > C.f * B.s + A.f * C.s + B.f * A.s);
}
int main()
{
int n;
in >> n;
for(int i = 1; i <= n; ++i)
in >> v[i].f >> v[i].s;
sort(v+1, v+n+1, cmp);
punct a, b;
a = v[1];
b = v[n];
for(int i = 2; i <= n - 1; ++i) {
if(!peste(a,b,v[i]))
v[i].ord=1;
else
v[i].ord=2;
}
st[1]=1;
vf = 1;
for(int i = 2; i <= n; ++i) {
if(v[i].ord == 1 || v[i].ord == 0)
{
while(vf > 1 && !peste(v[st[vf - 1]], v[st[vf]],v[i]))
vf--;
vf++;
st[vf]=i;
}
}
vfc = vf;
st[vfc]=n;
for(int i = n - 1; i >= 1; --i) {
if(v[i].ord == 2 || v[i].ord == 0)
{
while(vf > vfc && !peste(v[st[vf - 1]], v[st[vf]], v[i]))
vf--;
vf++;
st[vf]=i;
}
}
out << vf - 1 << '\n';
for(int i = 1; i < vf; ++i)
out << fixed << setprecision(6) << v[st[i]].f << " " << v[st[i]].s << " " << "\n";
return 0;
}