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

Post by ar2rd »

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

Post by jerk »

My code just got accepted. It is designed NOT to detect border hits (however I cannot confirm if the judge tests this scenario 8) ). 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 :wink: ) 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

Post by snar »

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.


Thanks in advance
Narek Saribekyan

ranban282
New poster
Posts: 37
Joined: Tue May 02, 2006 1:01 pm
Contact:

Post by ranban282 »

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.
Thanx in advance.

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

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

Post by waez »

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

Post by harrym »

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

Post by rickyliu »

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

Post by harrym »

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:

Post by cytmike »

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

Post by kodder »

i Got lots of WA :o :o :o
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

Post by helloneo »

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:

Post by kodder »

thank you

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

Re: Hi!

Post by pfiesteria »

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..

Thanks in advance :)
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

Post by pfiesteria »

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:

Post by Nedy88 »

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.

Post Reply

Return to “Volume 1 (100-199)”