Pagini recente » Cod sursa (job #1476268) | Cod sursa (job #2891293) | Cod sursa (job #2236908) | Cod sursa (job #1853737) | Cod sursa (job #688836)
Cod sursa(job #688836)
#include<cstdio>
#include<algorithm>
#define infile "infasuratoare.in"
#define outfile "infasuratoare.out"
#define n_max 120005
#define INF 1<<30
using namespace std;
struct punct {
double x, y; };
punct a[n_max];
int nxt[n_max], ST[n_max];
int N, P;
inline bool cmp( int i, int j)
{
return (a[i].x - a[P].x) * (a[j].y - a[P].y) < (a[j].x - a[P].x) * (a[i].y - a[P].y);
}
inline double semn(int i1, int i2, int i3){
return a[i1].x * a[i2].y + a[i3].x * a[i1].y + a[i2].x * a[i3].y - a[i3].x * a[i2].y - a[i2].x * a[i1].y - a[i1].x * a[i3].y; }
void citeste()
{
freopen(infile, "r", stdin);
scanf("%d",&N);
for(int i=1; i<=N; ++i)
scanf("%lf %lf",&a[i].x, &a[i].y);
fclose(stdin);
}
void rezolva()
{
a[P].x = a[P].y = INF;
for(int i=1; i<=N; ++i)
if(a[i].x < a[P].x || (a[i].x == a[P].x && a[i].y < a[P].y))
P = i;
for(int i =1; i<=N; ++i)
if(i != P)
nxt[++nxt[0]] = i;
sort(nxt+1, nxt + nxt[0] + 1, cmp);
ST[++ST[0]] = P;
for(int i=1; i<=nxt[0]; ++i)
{
if(nxt[i] == P)
continue;
while(ST[0] >= 2 && semn(ST[ST[0]-1], ST[ST[0]], nxt[i]) > 0)
ST[0]--;
ST[++ST[0]] = nxt[i];
}
}
void afiseaza()
{
freopen(outfile, "w", stdout);
printf("%d\n", ST[0]);
reverse(ST+1, ST + ST[0] + 1);
for(int i = 1; i <= ST[0] ; ++i)
printf("%lf %lf\n", a[ST[i]].x, a[ST[i]].y);
fclose(stdout);
}
int main()
{
citeste();
rezolva();
afiseaza();
return 0;
}