Pagini recente » Cod sursa (job #1685897) | Cod sursa (job #2278545) | Cod sursa (job #3208121) | Cod sursa (job #2019602) | Cod sursa (job #1237652)
#include <cstdio>
#include <algorithm>
FILE* in=fopen("infasuratoare.in","r");
FILE* out=fopen("infasuratoare.out","w");
const int Q=120007;
int n;
struct point{
double x,y;
} v[Q];
double clock(point a, point b, point c)
{
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
int s[Q];
void make_infasurare()
{
n++;
v[n].x=v[1].x;
v[n].y=v[1].y;
s[0]=2;
s[1]=1;
s[2]=2;
for(int i=3; i<=n; i++)
{
while(clock(v[s[s[0]-1]],v[s[s[0]]],v[i])==0)
{
if(v[s[s[0] ] ].x< v[s[s[0]-1]].x)
s[0]--;
else
{
v[s[s[0]-1]].x=v[s[s[0]]].x;
v[s[s[0]-1]].y=v[s[s[0]]].y;
s[0]--;
}
}
while(clock(v[s[s[0]-1]],v[s[s[0]]],v[i])<0)
{
s[0]--;
}
s[++s[0]]=i;
}
s[0]--;
n--;
fprintf(out,"%d\n",s[0]);
for(int i=1; i<=s[0]; i++)
{
fprintf(out,"%.6lf %.6lf\n",v[s[i]].x,v[s[i]].y);
}
}
bool cmp(point a, point b)
{
return clock(v[1],a,b)>0;
}
void find_min()
{
int dmin=1;
for(int i=2; i<=n; i++)
{
if(v[i].x==v[dmin].x && v[i].y<v[dmin].y)
dmin=i;
if(v[i].x<v[dmin].x)
dmin=i;
}
double aux;
aux=v[1].x;
v[1].x=v[dmin].x;
v[dmin].x=aux;
aux=v[1].y;
v[1].y=v[dmin].y;
v[dmin].y=aux;
}
int main()
{
fscanf(in,"%d",&n);
// inp>>n;
double k,q;
for(int i=1; i<=n; i++)
{
if(i==241)
{
i+=i;
i/=2;
}
//inp>>v[i].x>>v[i].y;
//fscanf(in,"%lf %lf",&k,&q);
fscanf(in,"%lf %lf",&v[i].x,&v[i].y);
// v[i].x+=0.0000001;
// v[i].y+=0.0000001;
}
find_min();
std::sort(v+2,v+n+1,cmp);
make_infasurare();
return 0;
}