Pagini recente » Cod sursa (job #833719) | Cod sursa (job #2554230) | Cod sursa (job #1981474) | Cod sursa (job #1766239) | Cod sursa (job #1401960)
#include <cstdio>
#include <algorithm>
using namespace std;
FILE *in, *out;
const int MAX_N = 100000;
const int INF = 1000000000;
long double dist(double x1, double y1, double x2, double y2)
{
return ((long double)(x1-x2)*(x1-x2) + (long double)(y1-y2)*(y1-y2));
}
struct point2Ddouble
{
double x, y;
};
point2Ddouble points[MAX_N];
point2Ddouble p0;
point2Ddouble elements[MAX_N];
int nre;
void push(point2Ddouble e)
{
elements[nre].x = e.x;
elements[nre].y = e.y;
nre++;
}
void pop()
{
nre--;
}
point2Ddouble top()
{
return elements[nre-1];
}
point2Ddouble nextToTop()
{
return elements[nre-2];
}
void change(int a, int b)
{
point2Ddouble aux;
aux.x = points[a].x;
aux.y = points[a].y;
points[a].x = points[b].x;
points[a].y = points[b].y;
points[b].x = aux.x;
points[b].y = aux.y;
}
long double ccw(point2Ddouble p1, point2Ddouble p2, point2Ddouble p3)
{
return ((long double)p1.x*p2.y+(long double)p2.x*p3.y+(long double)p3.x*p1.y-(long double)p1.y*p2.x-(long double)p2.y*p3.x-(long double)p3.y*p1.x);
}
bool cmp(point2Ddouble a, point2Ddouble b)
{
long double turn = ccw(p0,a,b);
if(turn == 0)
{
return (dist(p0.x,p0.y,a.x,a.y) < dist(p0.x,p0.y,b.x,b.y));
}
return (turn > 0);
}
int main()
{
in = fopen("infasuratoare.in", "r");
out = fopen("infasuratoare.out", "w");
int n, i;
int lowestPointIndex;
p0.y = INF;
fscanf(in, "%d", &n);
//in >> n;
for(i = 0; i < n; i++)
{
fscanf(in, "%lf%lf", &points[i].x, &points[i].y);
//in >> points[i].x >> points[i].y;
if(points[i].y < p0.y)
{
p0.y = points[i].y;
p0.x = points[i].x;
lowestPointIndex = i;
} else if(points[i].y == p0.y && points[i].x < p0.x)
{
p0.x = points[i].x;
lowestPointIndex = i;
}
}
change(0,lowestPointIndex);
nre = 0;
sort(points+1,points+n,cmp);
push(points[0]);
push(points[1]);
for(i = 2; i < n; i++)
{
while(nre >= 2 && ccw(nextToTop(),top(),points[i]) <= 0)
{
pop();
}
push(points[i]);
}
fprintf(out, "%d\n", nre);
for(i = 0; i < nre; i++)
{
fprintf(out, "%.12lf %.12lf\n", elements[i].x, elements[i].y);
}
fclose(in);
fclose(out);
return 0;
}