, .
:
nN<=100
M={di|diD,i=1,n}
D={(x,y) |x,yR}
: r1,r2,r3D, fϵ{0,-1,-2}.
:
LNG = (x1,y1),(x2,y2)
PER = LNG(d1,d2)+LNG(d2,d3)+LNG(d3,d1) (d1,d2,d3)
CHK = a, |(2-x1)*(3-y2)|=|(x3-x2)*(y2-y1)|, a=0; =1 ( , )
e=3, max=-2
n>=2,
max=-1
| i=1
|
|| j=i+1
||
per=PER(di,dj,de)
max<per, CHK (di,dj,de)=1, max=per, p1=i,p2=j,p3=e; j=j+1 || j<=e-1 ||i=i+1 | i<=e-2 |e=e+1 e<=n 3. , Const int N=100- , . : n n , , . : int n- (n<=N) pnt A[N] , - struct pnt{float x,y}, , - . : , . : struct max {float per, int p1,p2,p3} - , c , per , p1,p2 p3 . pnt A[N] , - struct pnt{float x,y}, , - .
Void IN(pnt A[N],int i) . .
A[N] , i .
Void OUT (pnt A[N],max n) . .
A[N] , n , .
Float LNG (pnt A[N],int a,int b) . PER.
A[N] , a,b , .
|
|
Float PER (pnt A[N],int a,int b,int c) , . , LNG.
A[N] , a,b,c .
Int CHECK_LINE (pnt A[N], int a, int b, int c) , . .
A[N] , a,b,c .
#include <stdio.h>
#include <conio.h>
#include <math.h>
#define N 100
struct pnt
{
float x;
float y;
};
struct max
{
int p1,p2,p3;
float per;
};
void IN (pnt A[N],int i)
{
scanf ("%f",&A[i].x);
scanf ("%f",&A[i].y);
}
void OUT (pnt A[N],max n)
{
printf ("%f %f, ",A[n.p1].x,A[n.p1].y);
printf ("%f %f, ",A[n.p2].x,A[n.p2].y);
printf ("%f %f",A[n.p3].x,A[n.p3].y);
}
float LNG (pnt A[N],int a,int b)
{
float lng;
lng=sqrt((A[a].x-A[b].x)*(A[a].x-A[b].x)+(A[a].y-A[b].y)*(A[a].y-A[b].y));
return lng;
}
float PER (pnt A[N],int a,int b,int c)
{
float per;
per=LNG(A,a,b);
per+=LNG (A,b,c);
per+=LNG (A,c,a);
return per;
}
int CHECK_LINE (pnt A[N],int a,int b,int c)
{
float k1,k2;
k1=(A[a].x-A[b].x)*(A[b].y-A[c].y);
k2=(A[a].y-A[b].y)*(A[b].x-A[c].x);
if (fabs(k1)!=fabs(k2)) return 1;
else return 0;
}
void main ()
{
int n,i,j,e;
float per;
pnt A[N];
max permax;
permax.per=-2;
printf ("Input number:");
scanf ("%d",&n);
if (n>2)
{
permax.per=-1;
for (e=0;e<n;e++)
{
printf ("Input %d x,y:",e+1);
IN (A,e);
if (e>1)
for (i=0;i<=(e-2);i++)
for (j=i+1;j<=(e-1);j++)
{
per=PER (A,i,j,e);
if (permax.per<per)
if (CHECK_LINE (A,i,j,e)==1)
{
permax.per=per;
permax.p1=i;
permax.p2=j;
permax.p3=e;
}
}
}
if (permax.per!=-1) OUT (A,permax);
else printf ("Error: All points on one line");
}
else printf ("Error: Need more points");
getch();
}
1)
: 2
: Error: Need more points"
2) ( )
: 3, (2,2),(3,3),(2,2)
: Error: All points on the one line
3) ( )
: 4, (2,4),(3,5),(-4,-2),(-1,1)
:Error: All points on the one line
4)
: 17, (2,0),(1;7),(-1.5,5.2),(6.1,-1.6),(0.2,-0.2),(2,0),(2,4),(3,5),(-4,-2),(-1,1),(3,3),(2,2),(4,5),(5,4),(6,5),(5,6),(0,0)
: (1,7),(6.1,-1.6),(-4,-2)
, ;
, , ;
.