就是判斷一個坐標(biāo)系里面的三角形內(nèi)有多少個整數(shù)點(diǎn)
就是枚舉所有的整數(shù)點(diǎn)然后判斷是否在三角形內(nèi)就是了。
判斷是否在三角形內(nèi)的方法就是求一下三部分的面積是否等于那個大三角形的面積
求面積可以用叉乘或者海倫公式
最好不要用實(shí)數(shù)來判等
因?yàn)槿切蔚拿娣e乘以2以后是個整數(shù)
所以判等的過程中就要使用整數(shù)來就可以了
注意輸出格式
1
#include<stdio.h>
2#include<string.h>
3#include<math.h>
4char map[50][50];
5int S(int a,int b,int c,int d)
6
{
7
int k;
8 k=a*d-b*c;
9 if(k<0)k=-k;
10 return k;
11
}
12int main()
13{
14// freopen("aaaaaaa.txt","w",stdout);
15 int x1,x2,x3,y1,y2,y3,mx,my,mmx,mmy,minx,miny,maxx,maxy,ss,s1,s2,s3,i,j,t;
16 while(scanf("%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3)!=EOF)
17
{
18 minx=1000000;maxx=-100000;
19 miny=1000000;maxy=-100000;
20 ss=S(x2-x1,y2-y1,x3-x1,y3-y1);
21 memset(map,0,sizeof(map));
22 mx=x1;if(x2>mx)mx=x2;if(x3>mx)mx=x3;
23 my=y1;if(y2>my)my=y2;if(y3>my)my=y3;
24 mmx=x1;if(x2<mmx)mmx=x2;if(x3<mmx)mmx=x3;
25 mmy=y1;if(y2<mmy)mmy=y2;if(y3<mmy)mmy=y3;
26 for(i=mmx;i<=mx;i++)
27 for(j=mmy;j<=my;j++)
28 {
29 s1=S(x1-i,y1-j,x2-i,y2-j);
30 s2=S(x1-i,y1-j,x3-i,y3-j);
31 s3=S(x2-i,y2-j,x3-i,y3-j);
32 if(s1 && s2 && s3 && (s1+s2+s3)==ss)
33 {
34 map[i+10][j+10]=1;
35 if(i+10<minx)minx=i+10;
36 if(i+10>maxx)maxx=i+10;
37 if(j+10>maxy)maxy=j+10;
38 if(j+10<miny)miny=j+10;
39
}
40 }
41 for(j=maxy;j>=miny;j--)
42 {
43 for(i=minx;i<=maxx;i++)if(map[i][j])t=i;
44 for(i=minx;i<=t;i++)
45 {
46 if(i!=minx)printf(" ");
47 if(map[i][j])printf("(%2d, %2d)",i-10,j-10);
48 else printf(" ");
49 }
50 printf("\n");
51 }
52 printf("\n");
53 }
54 return 0;
55}
56