Pagini recente » Cod sursa (job #2342003) | Cod sursa (job #1088859) | Cod sursa (job #322896) | Cod sursa (job #1930935) | Cod sursa (job #1667716)
#include <fstream>
#include <algorithm>
#include <cmath>
#define DMAX 120010
#define INF 1000000005
using namespace std;
FILE * fin = fopen("infasuratoare.in", "r");
FILE * fout = fopen("infasuratoare.out", "w");
struct punct{
double x, y;
};
bool compare(punct a, punct b)
{
int ra=sqrt(a.x*a.x+a.y*a.y), rb=sqrt(b.x*b.x+b.y*b.y);
return a.x*b.y<b.x*a.y || (a.x*b.y==b.x*a.y && ra>rb);
}
void citire();
void translatie();
void rez();
int n, nrsol;
punct v[DMAX], start;
punct sol[DMAX];
int main()
{
int i;
citire();
translatie();
sort(v, v+n, compare);
rez();
// fprintf(fout, "%lf %lf\n\n", start.x, start.y);
//
// for (i=0; i<n; i++)
// fprintf (fout, "%lf %lf\n", v[i].x, v[i].y);
//
fprintf(fout, "%d\n", nrsol);
for (i=nrsol-1; i>=0; i--)
fprintf(fout, "%lf %lf\n", sol[i].x+start.x, sol[i].y+start.y);
fclose(fin);
fclose(fout);
return 0;
}
void citire()
{
int i;
start.x=start.y=INF;
fscanf(fin, "%d", &n);
for (i=0; i<n; i++)
{
fscanf(fin, "%lf %lf", &v[i].x, &v[i].y);
if (v[i].y<start.y || (start.y == v[i].y && v[i].x<start.x))
start=v[i];
}
}
void translatie()
{
int i;
for (i=0 ;i<n; i++){
v[i].x-=start.x;
v[i].y-=start.y;
}
}
void rez()
{
int i, m, nr;
punct v1, v2, v3;
v1=v[0];
v2=v[1];
sol[nrsol++]=v1;
for (i=2; i<n; i++)
{
v3=v[i];
if (v1.x-v2.x==0) m=0;
else m=-(v1.y-v2.y)/(v1.x-v2.x);
nr=(v2.y-v3.y)-m*(v2.x-v3.x);
if (nr>0)
{
sol[nrsol++]=v2;
v1=v2;
v2=v3;
}
else
{
v2=v3;
}
}
sol[nrsol].x=sol[nrsol].y=0;
nrsol++;
}