Pagini recente » Autentificare | Cod sursa (job #757974) | Cod sursa (job #105439) | Cod sursa (job #2225948) | Cod sursa (job #1237643)
#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];
void verificare()
{
FILE* in1=fopen("infasuratoare.out","r");
FILE* in2=fopen("infasurare.ok","r");
char q[100],w[100];
int x=0;
while(fscanf(in1,"%s",q)>0)
{
x++;
fscanf(in2,"%s",w);
for(int i=0; i<60; i++)
{
if(q[i]!=w[i])
{
printf("%d",x/2);
return ;
}
if(q[i]==0)
break;
}
}
}
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();
fclose(in);
fclose(out);
verificare();
return 0;
}