Pagini recente » Cod sursa (job #762288) | Cod sursa (job #1478904) | Cod sursa (job #1095254) | Istoria paginii runda/cni_preoji/clasament | Cod sursa (job #1923180)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstdio>
#define NMAX 120001
#define inf 1000000001
using namespace std;
int N;
struct point {double x,y;} P[NMAX],REZ[NMAX];
double xmin=inf,ymin=inf;int imin,p=1,u=1;
void citire()
{
FILE *f=fopen("infasuratoare.in","r");
fscanf(f,"%d",&N);
for(int i=1;i<=N;i++)
{
fscanf(f,"%lf%lf",&P[i].x,&P[i].y);
if(P[i].x<xmin)
{
xmin=P[i].x;
ymin=P[i].y;
imin=i;
}
else
if(xmin==P[i].x&&ymin>P[i].y)
{
xmin=P[i].x;
ymin=P[i].y;
imin=i;
}
}
}
double det(point A,point B,point C)
{
return (A.x-B.x)*(C.y-B.y)-(A.y-B.y)*(C.x-B.x);
}
//A.x*B.y+B.x*C.y+A.y*C.x-B.y*C.x-A.x*C.y-B.x*A.y;
//(A.x-B.x)*(C.y-B.y)-(A.y-B.y)*(C.x-B.x)
int cmp(point A,point B)
{
return det(P[1],A,B)<0;
}
void rez()
{
swap(P[1],P[imin]);
sort(P+2,P+N+1,cmp);
REZ[1]=P[1];
REZ[2]=P[2];
u=2;
for(int i=3;i<=N;i++)
{
while((det(REZ[u-1],REZ[u],P[i])>0)&&u>2)
u--;
REZ[++u]=P[i];
}
FILE *f1=fopen("infasuratoare.out","w");
fprintf(f1,"%d\n",u);
for(int i=1;i<=u;i++)
fprintf(f1,"%lf %lf\n",REZ[i].x,REZ[i].y);
}
int main()
{
citire();
rez();
return 0;
}