Pagini recente » Cod sursa (job #1575665) | Cod sursa (job #2081126) | Cod sursa (job #405281) | Cod sursa (job #2260112) | Cod sursa (job #477196)
Cod sursa(job #477196)
// Infasuratoare convexa.cpp : Defines the entry point for the console application.
//
//#include "stdafx.h"
#include "stdio.h"
#include <algorithm>
#include "math.h"
using namespace std;
FILE *f=fopen("infasuratoare.in", "r");
FILE *g=fopen("infasuratoare.out", "w");
struct pct
{
double x, y;
};
int n;
pct v[120001];
int ind[120001];
int st[120001];
int pctin, pi;
bool cmpf(int i,int j)
{
return (double)(v[i].x - v[pctin].x) * (v[j].y - v[pctin].y) < (double)(v[j].x - v[pctin].x) * (v[i].y - v[pctin].y);
}
int comp(pct x, pct y)
{
if ( (x.x-v[pctin].x)*(y.y-v[pctin].y)<(y.x-v[pctin].x)*(x.y-v[pctin].y))
return 1;
return 0;
}
int semn(int i1, int im, int i2)
{
if ( v[i1].x*v[im].y+v[im].x*v[i2].y+v[i2].x*v[i1].y-v[i1].y*v[im].x-v[im].y*v[i2].x-v[i2].y*v[i1].x<0) return 0;
return 1;
}
void quicksort(int lo, int hi)
{
double h;
pct x=v[(lo+hi)/2];
int i=lo, j=hi;
do
{
while (comp(v[i], x)==1 && i<hi) i++;
while (comp(v[j], x)==0 && j>lo) j--;
if (i<=j)
{
h=v[i].x; v[i].x=v[j].x; v[j].x=h;
h=v[i].y; v[i].y=v[j].y; v[j].y=h;
i++; j--;
}
}
while (i<=j);
if (j>lo) quicksort(lo, j);
if (i<hi) quicksort(i, hi);
}
void read()
{
v[0].x=100000000000.00000;
fscanf(f, "%d", &n);
for (int i=1; i<=n; ++i)
{
fscanf(f, "%lf%lf", &v[i].x, &v[i].y);
if (v[i].x<v[pctin].x || v[i].x==v[pctin].x && v[i].y<v[pctin].y)
pctin=i;
}
}
int main()
{
read();
int pi=pctin;
pct aux=v[pi];
for (int i=1; i<=n; ++i)
{
if (i==pi) continue;
ind[++ind[0]]=i;
}
// quicksort(1, n);
sort(ind + 1,ind + ind[0] + 1,cmpf);
st[++st[0]]=pi;
for (int j=1; j<=ind[0]; ++j)
{
if (ind[j]==pi) continue;
while (st[0]>=2 && semn(st[st[0]-1], st[st[0]], ind[j])==1 )
--st[0];
st[++st[0]]=ind[j];
}
fprintf (g, "%d\n", st[0]);
fprintf(g, "%lf %lf\n", aux.x, aux.y);
for (int k=st[0]; k>1; --k)
fprintf(g, "%lf %lf\n", v[st[k]].x, v[st[k]].y);
return 0;
}