Posted on 2008-08-29 20:28
Hero 閱讀(146)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4
5 #define eps 1e-8
6 #define zero(x) ( ((x)>0?(x):-(x))<eps )
7 #define _sign(x) ((x)>eps?1:((x)<-eps?2:0))
8
9 struct Point
10 {
11 double x ;
12 double y ;
13 };
14 struct Point point[4] ;
15
16 double minx, miny ;
17 double maxx, maxy ;
18
19 double fmax( double a, double b )
20 {
21 if( a - b > 0 ) return a ;
22 else return b ;
23 }
24 double fmin( double a, double b )
25 {
26 if( a - b < 0 ) return a ;
27 else return b ;
28 }
29
30 double xmult( Point p1, Point p2, Point p0 ) {
31 return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
32 }
33
34 //判點(diǎn)在凸多邊形內(nèi)或多邊形邊上,頂點(diǎn)按順時(shí)針或逆時(shí)針給出
35 int inside_convex( Point q, int n, Point* p ) {
36 int s[3]={1,1,1};
37 for ( int i=0;i<n&&s[1]|s[2];i++ )
38 s[_sign(xmult(p[(i+1)%n],q,p[i]))]=0;
39 return s[1]|s[2];
40 }
41
42 int main()
43 {
44 while( scanf( "%lf %lf",&point[0].x,&point[0].y ) )
45 {
46 minx = 500 ; miny = 500 ;
47 maxx = -100 ; maxy = -100 ;
48
49 minx = fmin( minx, point[0].x ) ;
50 miny = fmin( miny, point[0].y ) ;
51 maxx = fmax( maxx, point[0].x ) ;
52 maxy = fmax( maxy, point[0].y ) ;
53
54 scanf( "%lf %lf",&point[1].x,&point[1].y ) ;
55
56 minx = fmin( minx, point[1].x ) ;
57 miny = fmin( miny, point[1].y ) ;
58 maxx = fmax( maxx, point[1].x ) ;
59 maxy = fmax( maxy, point[1].y ) ;
60
61 scanf( "%lf %lf",&point[2].x,&point[2].y ) ;
62
63 minx = fmin( minx, point[2].x ) ;
64 miny = fmin( miny, point[2].y ) ;
65 maxx = fmax( maxx, point[2].x ) ;
66 maxy = fmax( maxy, point[2].y ) ;
67
68 bool isbreak = true ;
69 for( int i=0; i<3; i++ )
70 {
71 if( !zero(point[i].x) )
72 {
73 isbreak = false ; break ;
74 }
75 if( !zero(point[i].y) )
76 {
77 isbreak = false ; break ;
78 }
79 }
80 if( isbreak ) break ;
81
82 int mini = (int)minx ; int maxi = (int)maxx + 1 ;
83 int minj = (int)miny ; int maxj = (int)maxy + 1 ;
84
85 int out = 0 ; struct Point q ;
86 for( int i=mini; i<=maxi; i++ )
87 {
88 for( int j=minj; j<=maxj; j++ )
89 {
90 q.x = i ; q.y = j ;
91 if( inside_convex( q, 3, point ) ) out++ ;
92 }
93 }
94
95 printf( "%4d\n", out ) ;
96 }
97
98 return 0 ;
99 }
100