Pagini recente » Rating Diaconu Diana (dianna) | Cod sursa (job #2297560) | Cod sursa (job #1738703) | Cod sursa (job #1282398) | Cod sursa (job #2700848)
#include <bits/stdc++.h>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct Punct
{
double x, y;
};
Punct P[120005];
int St[120005];
bool viz[120005];
double det(const Punct &a, const Punct &b, const Punct &c)
{
return (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);
}
bool ok(const Punct &a, const Punct &b)
{
if(a.x==b.x)
return a.y<b.y;
return a.x<b.x;
}
void solve(int &n,int &h)
{
sort(P + 1, P + n + 1, ok);
St[1] = 1;
St[2] = 2;
h=2;
viz[2] = 1;
for(int i = 3, p = 1; i >= 1; i += p)
{
if(viz[i]) continue;
while(h >= 2 && det(P[St[h - 1]], P[St[h]], P[i]) < 0)
viz[St[h--]]=0;
St[++h]=i;
viz[i] = 1;
if(i==n)
p = -1;
}
h--;
}
int main()
{
int n,h;
in >> n;
for(int i = 1; i <= n; i++)
in >> P[i].x >> P[i].y;
solve(n,h);
out << h << '\n';
out<< fixed << setprecision(6);
for(int i = 1; i <= h; i++)
out << P[St[i]].x << ' ' <<P[St[i]].y << '\n';
return 0;
}