Pagini recente » Cod sursa (job #1665115) | Cod sursa (job #3175196) | Cod sursa (job #1436640) | Cod sursa (job #1495658) | Cod sursa (job #1738433)
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
FILE *f=fopen("infasuratoare.in","r");
FILE *g=fopen("infasuratoare.out","w");
int N;
typedef struct {double x,y;} POINT;
POINT V[120005],p0;
POINT puncte[120005];
int i,poz;
POINT st[120005];
int orient(POINT A,POINT B,POINT C)
{
int val=(B.y-A.y)*(C.x-B.x)-(C.y-B.y)*(B.x-A.x);
if(val<0)
return -1;
if(val>0)
return 1;
return 0;
}
int dist(POINT a,POINT b)
{
return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));
}
bool comp(POINT a,POINT b)
{
int val=orient(p0,a,b);
if(val==0)
{
if(dist(a,p0)>=dist(b,p0))
return 0;
return 1;
}
if(val==-1)
return 1;
return 0;
}
void mysort(int st,int dr)
{
int i,j;
i=st;
j=dr;
POINT pivot=V[(st+dr)/2];
while(i<j)
{
while(comp(V[i],pivot))
i++;
while(!comp(V[j],pivot))
j--;
if(i<=j)
{
swap(V[i],V[j]);
i++;
j--;
}
}
if(i<dr)
mysort(i,dr);
if(j>st)
mysort(st,j);
}
int main()
{
fscanf(f,"%d",&N);
poz=1;
for(i=1;i<=N;i++)
{
fscanf(f,"%lf %lf",&V[i].x,&V[i].y);
if(V[i].y<V[poz].y||(V[i].y==V[poz].y&&V[i].x<V[poz].x))
poz=i;
}
swap(V[1],V[poz]);
p0=V[1];
sort(V+1,V+1+N,comp);
puncte[(int)(++puncte[0].x)]=V[1];
for(i=2;i<=N;i++)
{
while(i<N&&orient(p0,V[i],V[i+1])==0)
i++;
puncte[(int)(++puncte[0].x)]=V[i];
}
st[(int)(++st[0].x)]=puncte[1];
st[(int)(++st[0].x)]=puncte[2];
st[(int)(++st[0].x)]=puncte[3];
for(i=4;i<=puncte[0].x;i++)
{
while(orient(st[(int)(st[0].x-1)],st[(int)(st[0].x)],puncte[i])>=0)
{
st[0].x--;
}
st[(int)(++st[0].x)]=puncte[i];
}
fprintf(g,"%d\n",(int)st[0].x);
for(i=1;i<=st[0].x;i++)
{
fprintf(g,"%f %f\n",st[i].x,st[i].y);
}
fclose(f);
fclose(g);
return 0;
}