## 109 - SCUD Busters

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

ar2rd
New poster
Posts: 16
Joined: Sat Oct 22, 2005 2:05 am

### 109 WA

Can anybody help me with that problem? Judge says WA and I have no idea what could be wrong. Thanks in advance, for replies.

Code: Select all

``````//SCUD Busters - acm.uva.es/p/v1/109.html
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <cstring>
#include <climits>
#include <cmath>
#include <algorithm>
#include <vector>
#define REP(i,n) for(int tn = n, i = 0; i < tn; ++i)
#define FOR(i,a,b) for(int i = (a),tb = (b);i <= tb; ++i)
#define FORD(i,a,b) for(int i = (a),tb = (b);i >= tb; --i)
#define INF INT_MAX
#define MAXK 22
#define MAXP 102

typedef long LL;

using namespace std;

struct Point {
Point(){}
Point(LL x, LL y):x(x),y(y) {}
LL x,y;
}kng[MAXK][MAXP];

LL N,x,y,i,nk=0,np[MAXK];
double area[MAXK];
bool destroyed[MAXK];
vector<Point> hull;

bool  operator==(const Point &a, const Point &b) { return a.x == b.x && a.y == b.y; }
Point operator-(const Point &a, const Point &b) { return Point(a.x - b.x, a.y - b.y); }
LL   operator^(const Point &a, const Point &b) { return a.x*b.y - b.x*a.y; }

bool compareCoordinates(const Point &a, const Point &b) {
if(a.y == b.y) return a.x < b.x;
return a.y < b.y;
}
bool comparePolarAngles(const Point &a, const Point &b) {
Point a1 = a-kng[nk][0], b1 = b-kng[nk][0];
double
ma = a1.x != 0 ? double(a1.y)/a1.x : INT_MAX,
mb = b1.x != 0 ? double(b1.y)/b1.x : INT_MAX;

if(ma < 0 && mb < 0)return -ma < -mb;
if(ma < 0)return 0;
if(mb < 0)return 1;
return  ma < mb;
}
bool isInside(Point a, int n)
{
int i, j, c = 0;
for (i = 0, j = np[n]-1; i < np[n]; j = i++) {
if ((((kng[n][i].y <= a.y) && (y < kng[n][j].y)) ||
((kng[n][j].y <= y) && (y < kng[n][i].y))) &&
(x < (kng[n][j].x - kng[n][i].x) * (y - kng[n][i].y) / (kng[n][j].y - kng[n][i].y) + kng[n][i].x))
c = !c;
}
return c;
}
double findPolygonArea(){
int res = 0;

REP(i,hull.size()) res += hull[i]^hull[(i+1)%hull.size()];

if(res<0)res = - res;

return res*0.5;
}
void findConvexHull() {

int nh=0;

sort(&kng[nk][0], &kng[nk][N],compareCoordinates);
sort(&kng[nk][1], &kng[nk][N], comparePolarAngles);
reverse(&kng[nk][0], &kng[nk][N]);

hull.clear();
hull.push_back(kng[nk][0]); nh++;

FOR(i,1,N-1){
Point p = kng[nk][i];
while(nh >= 2 && ((p-hull[nh-2])^(p-hull[nh-1])) >= 0) { hull.pop_back(); nh--;}

hull.push_back(p); nh++;
}

area[nk] = findPolygonArea();

np[nk] = hull.size();

REP(i, hull.size()) kng[nk][i] = hull[i];
}
int main() {

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif

memset(kng, 0, sizeof(kng));
memset(np,  0, sizeof(np));
memset(area,0, sizeof(area));
memset(destroyed, 0, sizeof(destroyed));

while(1) {

scanf("%d", &N);

if(N == -1)break;

np[nk] = N;

REP(i,N) scanf("%d %d",&kng[nk][i].x, &kng[nk][i].y);

findConvexHull();

nk++;
}

while(scanf("%d %d", &x, &y) == 2){
REP(i, nk)
if(isInside(Point(x,y), i))
destroyed[i] = 1;
}

double ret = 0.0;

REP(i,nk) ret += destroyed[i] ? (double)area[i] : 0.0;

printf("%.2f\n", ret);
}

``````
You're never too old to become younger...

jerk
New poster
Posts: 1
Joined: Mon Jan 16, 2006 10:16 pm
My code just got accepted. It is designed NOT to detect border hits (however I cannot confirm if the judge tests this scenario ). Just to let you know because I really missed this small piece of information. Should anyone wish I can post it here but it was designed to spare memory resourses and CPU cycles (professional deformation ) instead of being readable. It contains no comments (except the ones at my auxilary sheet of paper), I used funny and slang variable names in my native language etc. I can hint that I didn't use any float (or even double) variables (only int's and occasioanly long ints, you never know if the test system uses some old 16-bit integers) except till the very end when I needed to apply the half of the area formula. No other functions like sin, cos, tan, sqrt or their inverses, only +, - and *. Oh yes, understanding the cross product is an efficient weapon....

If you test at many examples but despite the same results as the AC code you get a WA, thoroughly check it (i.e. display the wall coordinates) the following kingdom:

5
10 10
12 12
15 15
10 11
13 13

Try other orders of the same coordinates as well. It really helped me to find a bug in my code.

snar
New poster
Posts: 44
Joined: Thu Sep 01, 2005 12:14 pm
Location: Yerevan, Armenia

### 109 SCUD Busters - WA

Someone, Help!

I'm using GrahamScan method for buiding a Convex Hull.
Can someone tell me where I've mistaken? First, asume that my GrahamScan function works correctly, is everything ok?. I want to be sure I understood problem correctly.

Also, there are some undefined cases in the problem statement.

1. Missile attacks the boundary of two kingdoms. Which one of them is considered to be attacked (both or none)?

2. Power plant can be placed at the boundary of kingdom(vertex of convex hull) and when missile lands within the walls of that country and destroys that country's power plant(vertex of convex hull), should I re-build my convex hull again?

Code: Select all

``````// 109 SCUD Busters

#include <vector>
#include <algorithm>

using namespace std ;

struct P        { int x, y; P() {}; P( int q, int w ) : x( q ), y( w ) {}         };

P operator +    ( const P p, const P q ) { P u( p.x + q.x, p.y + q.y ); return u; }
P operator -    ( const P p, const P q ) { P u( p.x - q.x, p.y - q.y ); return u; }
bool operator ==( const P p, const P q ) { return p.x == q.x && p.y == q.y ;      }
bool operator < ( const P p, const P q )
{
return p.x == 0 && p.y == 0 ? 1 : p.x * q.y - p.y * q.x < 0;
}

void Sort ( vector<P> &p, P q )
{
int i, n = p.size() ;
for  ( i=0; i<n; i++) p[i] = p[i] - q;
sort ( p.begin(), p.end() );
for  ( i=0; i<n; i++) p[i] = p[i] + q;
}

vector<P> GrahamScan ( vector<P> Q )
{

P> S;
P m, u, v, p;
int i, n = Q.size();

m = Q[0];
for ( i=1; i<n; i++ )
if ( Q[i].y < m.y )
m = Q[i];
else if ( Q[i].y == m.y )
if ( Q[i].x < m.x )
m = Q[i];

Sort ( Q, m );

S.push_back ( Q[0] );
S.push_back ( Q[1] );
S.push_back ( Q[2] );

for ( i=3; i<n; i++ )
{
u = S [ S.size () - 2 ];
v = S [ S.size () - 1 ];
p = Q [ i ];
while ( ( p - u ).x * ( v - u ).y - ( p - u ).y * ( v - u ).x <= 0 )
{
S.pop_back ( );
u = S [ S.size () - 2 ];
v = S [ S.size () - 1 ];
}
S.push_back ( p );
}
return S;
}

bool IsPointInsideConvexPolygon ( vector<P> p, P q )
{
int i,j, n = p.size() ;
for ( j=0,i=n-1; j<n; i=j++ )
if ( ( q - p[i] ).x * ( p[j] - p[i] ).y - ( q - p[i] ).y * ( p[j] - p[i] ).x < 0 )
return false;
return true;
}

double PolygonArea ( vector<P> p )
{
int i, j, n = p.size();
double A = 0.0;
for ( j=0,i=n-1 ; j<n ; i=j++ )
A += p[j].x * p[i].y - p[i].x * p[j].y ;
return abs( A ) / 2.0 ;
}

#include <stdio.h>
#define MAX 100

void main() {
vector<P> T[MAX], Q;
P p;
int color[MAX], n, i, N ;
double TotalArea ;
N = 0;
while   ( scanf ( "%d", &n ), n != -1 ) {
for ( i=0 ; i<n ; i++ ) {
scanf( "%d%d", &p.x, &p.y ) ;
T[N].push_back ( p ) ;
}
N ++;
}

for ( i=0 ; i<N ; i++ ) {
Q.push_back ( T[i].front( ) ) ;
T[i] = GrahamScan ( T[i]    ) ;
color[i] = 0;
}

TotalArea = 0.0 ;
while   (1) {
scanf ( "%d%d", &p.x, &p.y ) ;
if    (feof ( stdin ) ) break;
for   ( i=0 ; i<N; i++ )
if ( IsPointInsideConvexPolygon ( T[i], p ) ) {
TotalArea += color[i] ? 0 : PolygonArea ( T[i] ) ;
color[i] = 1;
break;
}
}
printf ( "%.2lf\n", TotalArea ) ;
}``````
See some explantions,
1. Identifier color is used to avoid re-counting total area in case of some missiles attack kingdom twice or more.
2. Function IsPointInsideConvexPolygon works correctly for only points sorted in a clockwise direction.
3. Operators <, +, - are used to sort points by their polar angles from the bottom-most point (say p) in pointset. I'm moving p to point 0,0 for easier sorting.

Narek Saribekyan

ranban282
New poster
Posts: 37
Joined: Tue May 02, 2006 1:01 pm
Contact:
Hi,
I'm trying to solve promlem 109 .
The way i'm doing it is aby finding the convex hull of the kingdoms and seeing if the missile lands within it. Then add the areas of the kingdom and print it.

Here's the code:

Code: Select all

``````#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<list>
#include<queue>
#include<cctype>
#include<stack>
using namespace std;
double slope(double x1,double y1,double x2,double y2)
{
double dely=(y2-y1),delx=(x2-x1),pi_2=acos(0.0);
if(dely==0.0)
return (delx>=0.0?0.0:2.0*pi_2);
else if(delx==0.0)
return (dely>=0.0?pi_2:3.0*pi_2);
else
{
double angle=atan(dely/delx);
if(delx>0.0 && dely>0.0)
return angle;
else if(delx<0.0)
return angle+2.0*pi_2;
else
return angle+4.0*pi_2;
}
}

bool cmp(vector<double>p1,vector<double> p2)
{
if(p1[1]<p2[1])
return 1;
else if(p1[1]>p2[1])
return 0;
else
return p1[0]<p2[0];
}

bool cmp1(vector<double> v1,vector<double> v2)
{
if(v1[2]==v2[2])
return v1[1]<v2[1];
else
return v1[2]<v2[2];
}

vector<double> next_to_top(vector<vector<double> > s)
{
vector<double> p1(2,0.0);
if(s.size()>=2)
{
vector<vector<double> >::iterator i=s.end()-2;
p1=*i;
}
return p1;
}

bool nonleftturn(vector<double> p1,vector<double> p2,vector<double> p3)
{
pair<double,double> v1(p3[0]-p1[0],p3[1]-p1[1]),v2(p2[0]-p1[0],p2[1]-p1[1]);
return ((v1.first*v2.second-v1.second*v2.first)>=0?1:0);

}

vector<vector<double> > convexhull(vector<vector<double> > v,int n)
{
vector<double> row(3);
vector<vector<double> > vertex(n,row);
for(int i=0;i<n;i++)
{
vertex[i][0]=v[i][0];
vertex[i][1]=v[i][1];
}
vector<vector<double> >::iterator temp=(min_element(vertex.begin(),vertex.end(),cmp));
double p0x=(*temp)[0],p0y=(*temp)[1];
//cout<<p0y<<" "<<p0y<<endl;
for(int i=0;i<n;i++)
{
vertex[i][2]=slope(p0x,p0y,vertex[i][0],vertex[i][1]);
}

sort(vertex.begin(),vertex.end(),cmp1);
/*for(vector<vector<double> >::iterator i=vertex.begin();i!=vertex.end();i++)

{
cout<<(*i)[0]<<" "<<(*i)[1]<<" "<<(*i)[2]<<endl;
}*/
vector<vector<double> > s;
s.push_back(vertex[0]);
s.push_back(vertex[1]);
s.push_back(vertex[2]);
for(int i=3;i<n;i++)
{
while (s.size()>=2 && nonleftturn(next_to_top(s),s.back(),vertex[i]))
{
s.pop_back();
}
s.push_back(vertex[i]);
}
//cout<<endl<<endl;
for(vector<vector<double> >::iterator i=s.begin();i!=s.end();i++)
{
cout<<(*i)[0]<<" "<<(*i)[1]<<endl;
}
return s;
}

double area_polygon(vector<vector<double> > vertices,int n)
{
double a=0.0;
for(int i=0;i<n-1;i++)
{
a+=(vertices[i][0]*vertices[i+1][1]-vertices[i+1][0]*vertices[i][1]);
}
a+=(vertices[n-1][0]*vertices[0][1]-vertices[0][0]*vertices[n-1][1]);
return a/2.0;
}

bool inside_polygon(vector<vector<double> >v,int n, vector<double> point)
{

int i, j, c = 0;
for (i = 0, j = n-1; i < n; j = i++) {
//cout<<i<<j<<endl;
if ((((v[i][1] <= point[1]) && (point[1] < v[j][1])) ||
((v[j][1] <= point[1]) && (point[1] < v[i][1]))) &&
(point[0] < (v[j][0] - v[i][0]) * (point[1] - v[i][1]) / (v[j][1] - v[i][1]) + v[i][0]))
c = !c;
}
return c;
}

int main()
{
vector<vector<vector<double> > > ch(20);
vector<int> flag;
int count=0;
while(1)
{

int n;
cin>>n;
if(n==-1)
break;
vector<double> p(2);
vector<vector<double> > kingdom(n,p);
for(int i=0;i<n;i++)
{
cin>>kingdom[i][0];
cin>>kingdom[i][1];
}
ch[count]=convexhull(kingdom,n);
//   cout<<area_polygon(ch[count],ch[count].size())<<endl;
flag.push_back(0);
count++;
}
vector<double> points(2);
while(cin>>points[0]>>points[1])
{
for(int i=0;i<(int)ch.size();i++)
{
if(inside_polygon(ch[i],ch[i].size(),points))
flag[i]=1;
}
}
double a=0.0;
for(int i=0;i<(int)flag.size();i++)
{
a+=(flag[i]?area_polygon(ch[i],ch[i].size()):0.0);
}
printf("%.2lf\n",a);
/*   points[0]=5;
points[1]=5;
cout<<inside_polygon(ch[0],6,points)<<endl;   */
return 0;
}
``````
I would be grateful if anyone could point out the flaw in my code and/or give me some test cases apart from the ones already given.

waez
New poster
Posts: 1
Joined: Sun Jun 04, 2006 6:47 am
Contact:

### getting WA for 109. Can anyone pls give me hints why WA?

I am getting WA for 109. Here is my code . I will be glad if anyone findout & inform me why I am getting WA or give me any sample input & output for which my code produce WA.

Code: Select all

``I solved it ...........so now I am now removing the code``

harrym
New poster
Posts: 5
Joined: Thu Sep 07, 2006 8:48 pm

### [resolved] 109 - WA

Have looked at every post I could find here and tried all of the test cases and for each one someone has claimed that thier ACC code gets the same answer as mine yet, still WA when submitted, anyone have any test cases mine gets wrong that the judge could use? sugestions on how to fix my code ...

Code: Select all

``````re-wrote the code and got AC
``````
Last edited by harrym on Sun Apr 08, 2007 11:31 pm, edited 1 time in total.

rickyliu
New poster
Posts: 30
Joined: Thu Sep 28, 2006 7:16 am
I think it may be the problem after the calling to sites.erase(). After the call, it will invalidate all iterators that refer to the following elements. So, the call should be changed as follows:

Code: Select all

``````iter = sites.erase(iter) - 1;
``````

harrym
New poster
Posts: 5
Joined: Thu Sep 07, 2006 8:48 pm
rickyliu wrote:I think it may be the problem after the calling to sites.erase(). After the call, it will invalidate all iterators that refer to the following elements. So, the call should be changed as follows:

Code: Select all

``````iter = sites.erase(iter) - 1;
``````
Shouldnt be a problem since the next statement breaks from that loop, the problem description does say no two hulls will overlap doesnt it?

cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:
There is only 1 test case in this problem.

Code: Select all

``````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
``````
The answer is 84350.00
Impossible is Nothing.

kodder
New poster
Posts: 6
Joined: Mon Apr 10, 2006 6:19 am
Location: china
Contact:

### 109 SCUD Busters

i Got lots of WA
can anyone help me!! where my error is!
the WA code are below:

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define PREC	0.000000001
#define MINX	-1
#define MINY	-1
#define MAXKINGDOM	21
#define MAXWALL		101

//#define DEBUG

typedef struct point {
int	x, y;
} Point;
typedef struct lineSeg {
Point	a, b;
} lineSeg;

struct kingdom {
int	n;
double	area;
Point	wall[MAXWALL];
} kingdom[21];

int convexHull2(Point hull[], int num_points);

int max(int a, int b)
{
return a > b ? a : b;
}
int min(int a, int b)
{
return a < b ? a : b;
}
//P1P0 X P2P0
// if return value big than zero~ p2p1 is clockwise.
double crossProduct(Point p0, Point p1, Point p2)
{
return (p1.x-p0.x)*(p2.y-p0.y) - (p2.x-p0.x)*(p1.y-p0.y);
}
int onSeg(Point a, Point b, Point p)
{
if (fabs(crossProduct(p, a, b)) < PREC) {
if (p.x >= min(a.x, b.x)
&& p.x <= max(a.x, b.x)
&& p.y >= min(a.y, b.y)
&& p.y <= max(a.y, b.y))
return 1;
}
return 0;
}
int segCross(Point p1, Point p2, Point p3, Point p4)
{
double 	d1 = crossProduct(p1, p3, p4);
double 	d2 = crossProduct(p2, p3, p4);
double 	d3 = crossProduct(p3, p1, p2);
double 	d4 = crossProduct(p4, p1, p2);

if (((d1 < 0 && d2 > 0) || (d1 > 0 && d2 < 0) ) &&
((d3 < 0 && d4 > 0) || (d3 > 0 && d4 < 0)))
return 1;
if (fabs(d1) < PREC && onSeg(p3, p4, p1)) return 1;
if (fabs(d2) < PREC && onSeg(p3, p4, p2)) return 1;
if (fabs(d3) < PREC && onSeg(p1, p2, p3)) return 1;
if (fabs(d4) < PREC && onSeg(p1, p2, p4)) return 1;
return 0;
}
int inPolygon(Point p[], int n, Point pt)
{
int	i, j, cnt;
Point	p2;

p[n] = p[0];
for (i = cnt = 0; i < n; i++) {
if (onSeg(p[i], p[i + 1], pt)) {
for (j = 0; j < n; j++) {
if (p[j].x == pt.x && p[j].y == pt.y) return 0;
}
return 1;
}
if (p[i].y != p[i + 1].y) {
p2.x = MINX;
p2.y = pt.y;
if (onSeg(p2, pt, p[i]) && p[i].y > p[i + 1].y) cnt++;
else if (onSeg(p2, pt, p[i + 1]) && p[i + 1].y > p[i].y) cnt++;
else if (segCross(p2, pt, p[i], p[i + 1])) cnt++;
}
}
return cnt % 2;
}
int inPolygon_2(Point p[], int n, Point pt)
{
Point	list[3];
int	i;

for (i = 0; i < n - 1; i++) {
if (crossProduct(pt, p[i], p[i + 1]) < 0)
return 0;
}
return 1;
}
int convexHull(Point p[], int n, Point p2[])
{
Point	tp;
int	i, j, m, min;
double	crossVal;

for (j = 0, i = 1; i < n; i++) {
if (p[j].y > p[i].y || (p[j].y == p[i].y && p[j].x > p[i].x))
j = i;
}
tp = p[j];
p[j] = p[0];
p[0] = tp;
for (i = 1; i < n; i++) {
min = i;
for (j = i + 1; j < n; j++) {
if ((crossVal = crossProduct(p[0], p[min], p[j])) < PREC)
min = j;
else if (fabs(crossVal) < PREC && p[j].x > p[min].x) {
min = j;
}
}
tp = p[i];
p[i] = p[min];
p[min] = tp;
}
p2[0] = p[0];
p2[1] = p[1];
p2[2] = p[2];
m = 2;
for (i = 3; i < n; i++) {
while (crossProduct(p2[m - 1], p2[m], p[i]) < 0)
m--;
p2[++m] = p[i];
}
return m + 1;
}
double plogArea(Point p[], int n)
{
double	s;
int	i;

for (s = 0.0, i = 1; i < n - 1; i++) {
s += crossProduct(p[0], p[i], p[i + 1]);
}
return s/2;
}
Point		list[101];

int main(void)
{
Point	loc;
int	i, n;
int	size;
double	area;

n = 0;
while (scanf("%d", &size) != EOF && size != -1) {
for (i = 0; i < size; i++) {
scanf("%d %d", &list[i].x, &list[i].y);
}
kingdom[n].n = convexHull(list, size, kingdom[n].wall);
kingdom[n].area = plogArea(kingdom[n].wall, kingdom[n].n);
#ifdef DEBUG
printf("area %.2lf\n", kingdom[n].area);
#endif
n++;
}
area = 0.0;
while (scanf("%d %d", &loc.x, &loc.y) != EOF) {
#ifdef DEBUG
if (!loc.x) break;
#endif
for (i = 0; i < n; i++) {
if (inPolygon(kingdom[i].wall, kingdom[i].n, loc)) {
area += kingdom[i].area;
kingdom[i].area = 0.0;
}
}
}
printf("%.2lf", area);
return 0;
}

``````

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
There is a thread on this problem already.. Don't create a new thread..
Use this one..

http://online-judge.uva.es/board/viewtopic.php?t=1100

kodder
New poster
Posts: 6
Joined: Mon Apr 10, 2006 6:19 am
Location: china
Contact:
thank you

pfiesteria
New poster
Posts: 9
Joined: Mon Aug 13, 2007 7:45 am

### Re: Hi!

cyfra wrote:Hi!

I am also trying to solve this problem...

I don't know what's wrong...

If SCUD hits the wall than is it counter as it hit the convex polygon or not ??

Could anyone who got AC tell me what is is output for this input:
4
0 0
1 1
1 0
0 1
4
10 10
20 10
20 20
10 20
-1
1 1
15 10
And could anyone give the right answers for seolv's inputs..

My AC code output 1.00 , I think there is no test case at point or on the wall.

pfiesteria
New poster
Posts: 9
Joined: Mon Aug 13, 2007 7:45 am

### Re: [109] SCUD Busters

seolv wrote:hi~

I am trying to solve this problem but I keep receiving WA.

I really don't know why my solution doesn't work.

In the problem description,

Each SCUD missile (anitary leansing niversal estroyer) that lands within the walls of a kingdom destroys that kingdom's power plant (without loss of life).

when missile launched at one of the points that compose of Convexhull,

the kingdom is not destroyed.. right? If the missile fired at the position of

power plant that is also a point composing of Convexhull, is the kingdom

destroyed?

my test input file and output are below. plz answer me.

12
3 3
4 6
4 11
4 8
10 6
5 7
6 6
6 3
7 9
10 4
10 9
1 7
5
20 20
20 40
40 20
40 40
30 30
3
10 10
21 10
21 13
10
100 101
200 195
143 199
111 200
107 154
132 102
101 223
110 155
118 107
102 148
-1
3 3
20 40
150 150
My AC code output 7961.00
seolv wrote: 12
3 3
4 6
4 11
4 8
10 6
5 7
6 6
6 3
7 9
10 4
10 9
1 7
5
20 20
20 40
40 20
40 40
30 30
3
10 10
21 10
21 13
10
100 101
200 195
143 199
111 200
107 154
132 102
101 223
110 155
118 107
102 148
-1
6 6
20 40
110 195
My AC code also output 7961.00

Nedy88
New poster
Posts: 1
Joined: Sun Sep 02, 2007 8:33 pm
Contact:
Hi,
I'm working on this problem, bus still get WA. I don't count missile attacks on the walls and on the points.

Here is my code:

Code: Select all

``````#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
#include <sstream>
using namespace std;

struct Point {
int x;
int y;
void dump();
};

void Point::dump() {
cout<<"Point ("<<x<<","<<y<<")"<<endl;
}

Point operator-(const Point& p1, const Point& p2) {
Point ret;
ret.x = p1.x-p2.x;
ret.y = p1.y-p2.y;
return ret;
}

Point operator+(const Point& p1, const Point& p2) {
Point ret;
ret.x = p1.x+p2.x;
ret.y = p1.y+p2.y;
return ret;
}

Point accPoint;

struct Kingdom {
vector<Point> pts;
vector<Point> ch;
bool destroyed;
double area;
};

int crossProduct(Point a,Point b) {
return a.x*b.y - b.x*a.y;
}

bool operator<(const Point& pp1, const Point& pp2) {
Point p1 = pp1-accPoint;
Point p2 = pp2-accPoint;
int q1=0,q2=0;
if(p1.x>0 && p1.y>=0) q1=1;
else if(p1.x<=0 && p1.y>0)q1=2;
else if(p1.x<0 && p1.y<=0)q1=3;
else if(p1.x>=0 && p1.y<0)q1=4;
if(p2.x>0 && p2.y>=0) q2=1;
else if(p2.x<=0 && p2.y>0)q2=2;
else if(p2.x<0 && p2.y<=0)q2=3;
else if(p2.x>=0 && p2.y<0)q2=4;
if(q1<q2)return true;
else if(q1>q2)return false;
else {
if(crossProduct(p1,p2)>0)return true;
else if(crossProduct(p1,p2)<0)return false;
else {
int mag1,mag2;
mag1 = p1.x*p1.x + p1.y*p1.y;
mag2 = p2.x*p2.x + p2.y*p2.y;
if(mag1<mag2)return true;
else return false;
}
}
}

bool leftturn(Point p1,Point p2,Point p3) {
Point a,b;
a=p2-p1;
b=p3-p1;
if(crossProduct(b,a)<0)return true;
else return false;
}

int main() {
int i;
int n;
vector<Kingdom> kings;
vector<Point> attacks;
while(cin>>n) {
if(n==-1)break;
kings.resize(kings.size()+1);
kings[kings.size()-1].destroyed=false;
for(i=0;i<n;i++) {
Point tmp;
cin>>tmp.x>>tmp.y;
kings[kings.size()-1].pts.push_back(tmp);
}
}
int x,y;
while(cin>>x) {
if(x==-1)break;
cin>>y;
Point tmp;
tmp.x=x;
tmp.y=y;
attacks.push_back(tmp);
}
// finding convex hulls
int j;
vector<Point> m;
double ret=0.0;
string str;
for(i=0;i<kings.size();i++) {
Point minPoint=kings[i].pts[0];
for(j=1;j<kings[i].pts.size();j++) {
if(kings[i].pts[j].y<minPoint.y) {
minPoint = kings[i].pts[j];
}
else if(kings[i].pts[j].y==minPoint.y) {
if(kings[i].pts[j].x<minPoint.x) {
minPoint = kings[i].pts[j];
}
}
}
accPoint = minPoint;
sort(kings[i].pts.begin(),kings[i].pts.end());
m.resize(0);
for(j=1;j<kings[i].pts.size()-1;j++) {
if(crossProduct(kings[i].pts[j],kings[i].pts[j+1])!=0) {
m.push_back(kings[i].pts[j]);
}
}
m.push_back(kings[i].pts[j]);
kings[i].ch.resize(0);
kings[i].ch.push_back(minPoint);
kings[i].ch.push_back(m[0]);
kings[i].ch.push_back(m[1]);
for(j=2;j<m.size();j++) {
int si=kings[i].ch.size()-1;
while(!leftturn(kings[i].ch[si-1],kings[i].ch[si],m[j])){kings[i].ch.resize(si);si--;}
kings[i].ch.push_back(m[j]);
}
kings[i].ch.push_back(kings[i].ch[0]);
kings[i].area=0.0;
for(j=1;j<kings[i].ch.size();j++) {
kings[i].area += crossProduct(kings[i].ch[j-1],kings[i].ch[j]);
}
kings[i].area /= 2.0;
int k;
bool b=true;
for(j=0;j<attacks.size();j++) {
b=true;
for(k=0;k<kings[i].ch.size()-1;k++) {
if(!leftturn(kings[i].ch[k],kings[i].ch[k+1],attacks[j])){b=false;}
}
if(b){ret += kings[i].area;kings[i].destroyed=true;break;}
}
}
cout.setf(ios::fixed,ios::floatfield);
cout.precision(2);
cout<<ret<<endl;
return 0;
}
``````
If someone can tell me where is the problem or give more example tests.

EDIT: Never mind, I've found my bug.
Dreamer I am, and my dream is MIT.