pku 1264 SCUD Busters 凸包+点在形内判断+面积计算

题意:
有n个国家,国家里有若干个房子(。。怎么觉得这个是城市呢。。),国家的边界是包含所有房子的周长最短的多边形。
然后国家之间干仗,互相发射炮弹。给出炮弹落点坐标,问被攻击国家的总面积

解法:
这题标程有问题的。。但答案凑巧是对的。。。我用几何画板分析了下标程和数据,发现测试数据里第2个城市和第9个城市标程计算的凸包少了一个点。。。。
现在说下正解吧。。。
计算凸包不要多说了,这题甚至不用水平序,应为构造严格的凸包也可以。
然后计算面积是经典的三角剖分
计算点是否在形内用射线法,直接构造一条水平射线,然后很简单的就讨论好了- -(注意:炮弹落在边界上算在形内~)

我的程序:
顺便下面把标程也贴出,大家也分析分析看看它怎么得出那么诡异的结果。。。
  1import 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)!=0return -(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)==0return 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==1return 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==-1break;
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

测试数据:
测试数据10
400 30
410 30
420 30
430 30
430 40
430 50
430 60
400 50
425 34
428 40
        20
        38        26
        24        23
        31        15
        25         3
         2        11
        35        28
        46        48
        30        32
         7        47
        44        41
         9        17
        32        34
         1        23
         7        38
        28        39
        14         3
        26        16
        31        38
        41         7
        18         6
        42
       373       391
       398       243
       399       205
       372       296
       377       254
       377       382
       395       214
       379       186
       375       207
       393       311
       398       341
       394       253
       385       237
       389       190
       386       122
       373       166
       392       270
       398       386
       389       289
       376       382
       397       343
       377       204
       390       301
       372       236
       376       329
       388       330
       380       121
       387       198
       390       324
       395       142
       382       137
       392       359
       395       117
       391       282
       387       226
       378       350
       377       227
       374       224
       397       344
       388       136
       397       106
       374       142
        60
        90       232
       104       127
        89       199
        73       174
        36       228
        30       175
        20       174
       110       226
        76       135
       112       122
        20       138
        64       141
       115       201
        98       132
        35       215
        78       136
        31       239
        70       173
       105       234
        91       128
        66       126
        63       235
        90       196
        91       163
        50       155
        57       196
        96       178
        18       235
       123       206
        55       229
       121       146
        23       248
        55       138
        11       203
        91       147
        40       213
        78       144
        99       215
        16       157
        74       181
        16       173
       109       247
       108       225
        64       240
        97       228
        13       232
       107       213
       108       139
       100       149
        61       233
        76       183
        87       212
        60       142
        63       177
       115       184
       114       122
       124       246
       100       218
        88       229
        87       151
        30
       139        36
       144        52
       223        67
       146        70
       224        48
       140        47
       163        36
       196        57
       153        55
       154        13
       137        18
       140        17
       227        14
       230        63
       142        43
       239        45
       159        23
       146        17
       141        17
       213        30
       234        69
       175        62
       201        25
       128        11
       137        63
       129        24
       169        20
       155        17
       128        25
       219        18
        40
       342        26
       306        60
       362        70
       282        46
       357        22
       272        64
       345        61
       276        42
       316        40
       298        23
       300        48
       342        35
       312        54
       363        69
       280        41
       326        57
       322        62
       353        66
       315        42
       318        68
       353        36
       282        45
       365        49
       368        29
       295        41
       367        32
       325        48
       293        55
       335        69
       310        28
       359        58
       329        68
       358        40
       355        41
       306        36
       334        36
       354        29
       347        59
       366        60
       290        57
        10
       202       239
       237       219
       238       214
       200       226
       208       221
       208       238
       232       215
       210       211
       205       214
       230       228
        62
       297       253
       291       212
       279       204
       285       182
       280       150
       261       170
       288       219
       297       274
       284       228
       265       272
       295       253
       267       188
       286       234
       261       203
       266       247
       283       247
       271       150
       281       186
       285       245
       293       159
       274       157
       288       261
       293       148
       288       225
       282       199
       269       257
       267       199
       263       198
       295       254
       283       157
       296       143
       263       160
       279       162
       297       227
       291       153
       269       242
       284       157
       267       268
       281       197
       293       262
       288       149
       279       147
       278       264
       288       221
       288       186
       274       178
       276       222
       290       202
       262       264
       300       232
       275       257
       299       168
       264       278
       275       159
       260       229
       288       170
       270       240
       284       166
       291       242
       262       180
       282       206
       262       197
        33
        89       281
       113       282
       111       275
       127       280
        97       282
       136       277
        85       288
       112       271
        72       266
       129       264
        94       277
       136       304
       113       261
       101       297
        93       266
       106       294
        79       292
       137       269
       110       297
        85       299
        80       262
       110       271
       100       281
       107       272
        90       286
       130       281
        92       294
       118       301
       112       261
        75       269
       132       307
       115       292
       128       264
        98
       114       463
        70       442
        70       404
        54       464
        27       401
        52       480
        54       466
        27       462
        55       416
        24       443
        69       399
        44       470
        98       456
        44       410
        44       435
        21       404
        82       405
        43       451
        39       399
        33       457
        62       428
        16       446
        32       475
        14       405
        84       447
        82       401
       109       399
        92       485
        17       450
       123       494
        20       423
        63       392
        78       462
        97       466
        47       476
        27       489
        59       468
        69       406
        45       451
        22       443
        80       487
       125       463
        73       434
       122       460
        80       451
       111       488
       117       460
        46       420
       124       441
        41       500
       117       417
       124       429
        71       422
       111       438
       119       474
        88       490
        79       444
       115       456
        40       400
        87       480
        95       478
        63       443
       100       456
        20       468
        95       467
       123       422
        88       456
       115       489
        51       406
       118       469
        85       416
        96       450
        29       411
        45       456
        61       430
        32       489
        57       403
        97       456
        48       403
       108       475
        21       391
        83       473
        88       468
       111       442
        35       497
        36       472
        46       479
       129       491
        72       436
       104       419
        32       491
        17       494
        75       449
        89       473
        73       482
       110       441
        38       454
        46       438
        51
       156       484
       368       390
       374       365
       145       424
       190       396
       191       479
       339       371
       207       353
       172       366
       325       433
       369       452
       331       396
       258       386
       293       355
       265       312
       150       340
       315       407
       370       481
       291       419
       175       478
       360       453
       186       364
       299       427
       146       385
       179       445
       282       445
       209       311
       272       361
       297       442
       346       325
       230       322
       313       464
       344       309
       312       415
       276       378
       196       458
       184       379
       163       377
       357       454
       284       321
       362       302
       163       325
       257       329
       368       418
       331       316
       195       438
       288       321
       185       474
       270       376
       347       466
       316       310
-1
        33       485
       455       239
       467       176
        10       327
       101       256
       102       470
       397       189
       133       144
        64       178
       369       352
       458       402
       381       256
       236       228
       306       150
       249        36
        20       110
       349       283
       459       476
       303       315
        71       469
       439       404
        93       173
       318       336
        13       227
        78       382
       283       383
       138        36
       264       164
       314       374
       411        70
       180        62
       345       432
       407        29
       345       304
       272       209
       113       416
        89       211
        46       206
       433       407
       288        60
       443        11
        47        71
       235        81
       455       312
       382        48
       111       365
       296        62
        91       457
       260       203
       413       436
       352        32
       244        25
       232       441
       347       290
       351       164
       176       135
       206       294
       375       223
        34       441
       490       330
       195       417
       479       101
        57       492
       194        69
         5       318
       351       106
       132       357
       297        94
       385       364
425 35

答案:
 84350.00

posted on 2011-01-15 01:17 yzhw 阅读(758) 评论(0)  编辑 收藏 引用 所属分类: geometry&phycise


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

公告

统计系统

留言簿(1)

随笔分类(227)

文章分类(2)

OJ

最新随笔

搜索

积分与排名

最新评论

阅读排行榜