題意：
有n個國家，國家里有若干個房子（。。怎么覺得這個是城市呢。。），國家的邊界是包含所有房子的周長最短的多邊形。
然后國家之間干仗，互相發(fā)射炮彈。給出炮彈落點坐標，問被攻擊國家的總面積
解法：
這題標程有問題的。。但答案湊巧是對的。。。我用幾何畫板分析了下標程和數(shù)據(jù)，發(fā)現(xiàn)測試數(shù)據(jù)里第2個城市和第9個城市標程計算的凸包少了一個點。。。。
現(xiàn)在說下正解吧。。。
計算凸包不要多說了，這題甚至不用水平序，應(yīng)為構(gòu)造嚴格的凸包也可以。
然后計算面積是經(jīng)典的三角剖分
計算點是否在形內(nèi)用射線法，直接構(gòu)造一條水平射線，然后很簡單的就討論好了- -（注意：炮彈落在邊界上算在形內(nèi)~）
我的程序：
順便下面把標程也貼出，大家也分析分析看看它怎么得出那么詭異的結(jié)果。。。
1
import java.io.*;
2import java.util.*;
3class city
4
{
5
class pair implements Comparable<pair>
6
{
7 int x,y;
8 public int compareTo(pair pos)
9 {
10 if(-(x-ori.x)*(pos.y-ori.y)+(pos.x-ori.x)*(y-ori.y)!=0) return -(x-ori.x)*(pos.y-ori.y)+(pos.x-ori.x)*(y-ori.y);
11 else return -(pos.x-ori.x)*(pos.x-ori.x)-(pos.y-ori.y)*(pos.y-ori.y)+(x-ori.x)*(x-ori.x)+(y-ori.y)*(y-ori.y);
12
}
13 public String toString()
14 {
15 return " ["+x+","+y+"] ";
16 }
17 pair(int x,int y)
18 {
19 this.x=x;
20 this.y=y;
21
22 }
23 }
24 pair ori;
25 ArrayList<pair> point=new ArrayList<pair>();
26 void sort()
27 {
28 ori=new pair(Integer.MAX_VALUE,Integer.MAX_VALUE);
29 for(pair i:point)
30 if(i.y<ori.y||i.y==ori.y&&i.x<ori.x)
31 {
32 ori.y=i.y;
33 ori.x=i.x;
34 }
35 Collections.sort(point);
36 //凸包
37 ArrayList<pair> ans=new ArrayList<pair>();
38 for(pair i:point)
39 {
40 while(ans.size()>=2)
41 {
42 int x1=ans.get(ans.size()-1).x-ans.get(ans.size()-2).x,y1=ans.get(ans.size()-1).y-ans.get(ans.size()-2).y;
43 int x2=i.x-ans.get(ans.size()-1).x,y2=i.y-ans.get(ans.size()-1).y;
44 if(x2*y1-x1*y2>=0) ans.remove(ans.size()-1);
45 else break;
46 }
47 ans.add(i);
48 }
49 point=ans;
50 point.add(point.get(0));
51 }
52 void add(int x,int y)
53 {
54 point.add(new pair(x,y));
55 }
56 double aera()
57 {
58 double total=0;
59 for(int i=1;i<point.size()-1;i++)
60 {
61 int x1=point.get(i).x-point.get(0).x,y1=point.get(i).y-point.get(0).y;
62 int x2=point.get(i+1).x-point.get(0).x,y2=point.get(i+1).y-point.get(0).y;
63 total+=0.5*(x1*y2-x2*y1);
64 }
65 return total;
66 }
67 boolean isin(int x,int y)
68 {
69 int count=0;
70 for(int i=1;i<point.size();i++)
71 {
72 pair a=point.get(i-1),b=point.get(i);
73 if((x-a.x)*(b.y-a.y)-(y-a.y)*(b.x-a.x)==0) return true;
74 else
75 {
76 if(Math.min(a.y, b.y)>y||Math.max(a.y, b.y)<y) continue;
77 else
78 {
79 int x1,x2,y1,y2;
80 if(a.y>b.y)
81 {
82 x1=a.x-b.x;
83 y1=a.y-b.y;
84 x2=x-b.x;
85 y2=y-b.y;
86 }
87 else
88 {
89 x1=b.x-a.x;
90 y1=b.y-a.y;
91 x2=x-a.x;
92 y2=y-a.y;
93 }
94 if(x1*y2-x2*y1>=0) count++;
95 }
96 }
97 }
98 if(count%2==1) return true;
99 else return false;
100 }
101
}
102public class Main {
103 static city data[]=new city[21];
104 static int c=0;
105 public static void main(String[] args) {
106 Scanner in=new Scanner(System.in);
107 while(true)
108 {
109 int n=in.nextInt();
110 if(n==-1) break;
111 data[c]=new city();
112 while((n--)!=0)
113 data[c].add(in.nextInt(),in.nextInt());
114 data[c++].sort();
115 }
118
119 boolean used[]=new boolean[c];
120 Arrays.fill(used, false);
121 while(in.hasNextInt())
122 {
123 int x=in.nextInt(),y=in.nextInt();
124 for(int i=0;i<c;i++)
125 if(data[i].isin(x, y))
126 used[i]=true;
127
128 }
129 double ans=0;
130 for(int i=0;i<c;i++)
131 if(used[i])
132 ans+=data[i].aera();
133 System.out.printf("%.2f\n",ans);
134 }
135
136}
137
錯誤的標程：
1/**//*
2 * scud-busters solution
3 * V. Khera 29-OCT-1991
4 *
5 * compile with gcc
6 */
7
8#include <stdio.h>
9
10#define MAX_PTS 101 /* most number of points in kingdom */
11#define MAX_KING 20 /* most number of kingdoms */
12
13typedef struct point {
14 int x,y;
15} point_t;
16
17typedef struct kingdom {
18 int size; /**//* number of points in convex hull */
19 double area; /**//* total area of this polygon */
20 point_t list[MAX_PTS+1]; /**//* list of points in convex hull */
21} kingdom_t;
22
23
24static kingdom_t kingdoms[MAX_KING];
25static int num_kingdoms = 0;
26
27/**//* return the absolute value of an integer */
28static inline int abs(int x) { return x >= 0 ? x : -x; }
29
30/**//*
31 * return a value between 0.0 and 360.0 which is suitable for sorting
32 * points based on the angle the line segment p1,p2 makes with the
33 * positive horizontal. the value returned is not that angle, but has
34 * the same ordering properties.
35 */
36static const double theta(point_t p1, point_t p2)
37{
38 int dx, dy, ax, ay;
39 double t;
40
41 dx = p2.x-p1.x; ax = abs(dx);
42 dy = p2.y-p1.y; ay = abs(dy);
43
44 if ((dx == 0) && (dy == 0))
45 t = 0.0;
46 else
47 t = (double)dy / (ax+ay);
48
49 if (dx < 0)
50 t = 2.0 - t;
51 else if (dy < 0)
52 t = 4.0 + t;
53
54 return (t * 90.0);
55} /**//* theta */
56
57
58/**//*
59 * calculate the convex hull of a given set of points. the number of
60 * points defining the convex hull is the return value. the convex
61 * hull is built in-place in the array hull[]. the array passed must
62 * have room for one additional point at the end. num_points is the
63 * number of points in the array passed in. the convex hull list generated
64 * is in counterclockwise order and is closed.
65 */
66int convexHull(point_t hull[], int num_points)
67{
68 int i, min, num;
69 double minangle, v;
70 point_t t;
71
72 /**//* find the element with min y coordinate */
73 min = 0;
74 for (i = 1; i < num_points; ++i) {
75 if (hull[i].y < hull[min].y) min = i;
76 }
77
78 num = 0; /**//* no points in convex hull yet */
79 hull[num_points] = hull[min];
80 minangle = 0.0;
81
82 do {
83 t = hull[num]; hull[num] = hull[min]; hull[min] = t;
84 min = num_points;
85 v = minangle;
86 minangle = 360.0;
87 for (i = num+1; i <= num_points; ++i)
88 if ((theta(hull[num],hull[i]) > v) &&
89 (theta(hull[num],hull[i]) < minangle)) {
90 min = i;
91 minangle = theta(hull[num],hull[min]);
92 }
93 ++num;
94 } while ( min != num_points);
95 hull[num++] = hull[0]; /**//* close up polygon */
96 return num;
97} /**//* convexHull */
98
99
100/**//*
101 * read in a set of points from which to generate the convex hull. the
102 * parameter indicates how many points are specified, one point per line.
103 * the array is assumed to have enough space. reads from stdin.
104 */
105void readPoints(point_t p[], int num)
106{
107 while (num--) {
108 scanf("%d %d\n", &p[num].x, &p[num].y);
109 }
110} /**//* readPoints */
111
112
113/**//*
114 * calculate the area of a polygon given a list of points describing
115 * the polygon. the points may be listed in either clockwise or
116 * counterclockwise order. num is the number of points specified
117 * in the list. if the polygon array is given in clockwise order,
118 * the sign of the area will be negative. the last point in the polygon
119 * must be the same as the first.
120 */
121double polyArea(point_t p[], int num)
122{
123 double a = 0.0;
124 int i;
125
126 for (i = 1; i < num; ++i)
127 a += (double)p[i-1].x * p[i].y - (double)p[i].x * p[i-1].y;
128
129 return a/2;
130} /**//* polyArea */
131
132
133/**//*
134 * determine if the path from p0 to p1 to p2 is clockwise or
135 * counterclockwise. returns true if counterclockwise, false otherwise.
136 */
137int ccw(point_t p0, point_t p1, point_t p2)
138{
139 point_t list[4];
140
141 list[0] = list[3] = p0;
142 list[1] = p1;
143 list[2] = p2;
144
145 return (polyArea(list, 4) > 0);
146}
147
148/**//*
149 * determine if the given point is inside the specified convex
150 * polygon. the convex polygon must be listed in counterclockwise
151 * order. num indicates the number of points. returns 1 if inside,
152 * otherwise returns 0.
153 */
154int inPolygon(point_t p, point_t poly[], int num)
155{
156 int i;
157
158 for (i = 1; i < num; ++i) {
159 if (!ccw(poly[i-1],poly[i],p)) return 0;
160 }
161 return 1;
162} /**//* inPolygon */
163
164
165int main(void)
166{
167 int howMany, i;
168 double blackout = 0.0;
169 point_t p;
170
171 scanf("%d\n", &howMany);
172
173 /**//*
174 * read in the kingdom descriptions and calculate the convex
175 * hull and area associated with each. this is all we store.
176 */
177 while (howMany >= 0) {
178 readPoints(kingdoms[num_kingdoms].list, howMany);
179 kingdoms[num_kingdoms].size =
180 convexHull(kingdoms[num_kingdoms].list, howMany);
181 kingdoms[num_kingdoms].area =
182 polyArea(kingdoms[num_kingdoms].list,
183 kingdoms[num_kingdoms].size);
184#ifdef DEBUG
185 printf("size = %d\n",kingdoms[num_kingdoms].size);
186 for (howMany = 0; howMany < kingdoms[num_kingdoms].size; ++howMany) {
187 printf("(%d, %d)\n", kingdoms[num_kingdoms].list[howMany].x,
188 kingdoms[num_kingdoms].list[howMany].y);
189
190 }
191 printf("area: %.2lf\n", kingdoms[num_kingdoms].area);
192 putchar('\n');
193#endif /* DEBUG */
194 ++num_kingdoms;
195 scanf("%d\n", &howMany);
196 }
197
198 /**//*
199 * now read in the missile attacks and calculate which kingdom
200 * it fell in, if any. then add the area of that kingdom to
201 * the total.
202 */
203 while (scanf("%d %d\n", &p.x, &p.y) != EOF) {
204 for (i = 0; i < num_kingdoms; ++i) {
205 if (inPolygon(p, kingdoms[i].list, kingdoms[i].size)) {
206 blackout += kingdoms[i].area;
207 kingdoms[i].area = 0.0; /**//* not counted again */
208#ifdef DEBUG
209 printf("Hit! (%d,%d)\n",p.x,p.y);
210#endif
211 }
212#ifdef DEBUG
213 else printf("Miss! (%d,%d)\n",p.x,p.y);
214#endif
215
216 }
217#ifdef DEBUG
218 putchar('\n');
219#endif
220 }
221
222 printf ("%.2lf\n",blackout);
223 return 0;
224} /**//* main */
225
226
227
測試數(shù)據(jù)：
答案：
84350.00