Pagini recente » Cod sursa (job #1629479) | Cod sursa (job #500375) | Cod sursa (job #3213465) | Cod sursa (job #2301923) | Cod sursa (job #1667796)
#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 b.x*a.y < a.x*b.y || (a.x*b.y==b.x*a.y && ra>rb);
}
void citire();
void translatie();
void rez();
int prod(punct, punct, punct);
int n, nrs;
punct v[DMAX], start;
punct s[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+start.x, v[i].y+start.y);
//
fprintf(fout, "%d\n", nrs);
for (i=0; i<nrs; i++)
fprintf(fout, "%lf %lf\n", s[i].x+start.x, s[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, ok;
s[nrs++]=v[n-1];
s[nrs++]=v[0];
for (i=1; i<n-1; i++)
{
ok=prod(s[nrs-2], s[nrs-1], v[i]);
if (ok==0) //puncte coliniare
{
nrs--;
s[nrs++]=v[i];
}
else
{
if (ok>0) //la stanga
s[nrs++]=v[i];
else //la dreapta
{
while (ok<=0 && nrs>1)
{
nrs--;
ok=prod(s[nrs-2], s[nrs-1], v[i]);
}
s[nrs++]=v[i];
}
}
}
}
int prod(punct v1, punct v2, punct v3)
{
return (v2.x-v1.x)*(v3.y-v1.y)-(v3.x-v1.x)*(v2.y-v1.y);
}