OJ Board

Hello!

Need some examples on tricky input and its output. My program works for all input I've tried but get WA still.

My main idea.

Compute convex hull and area of all kingdoms. For each missile test inclusion and add area to sum if point inside walls.

Cheers,
Sarig

What if a kingdom is struck more than once ?

Tested and working. Also tested hits on borders and on corners. I hope I've interpreted this correctly.

A hit on a border does not affect a kingdom. Neither does a hit on a corner.

Cheers,
Sarig

Ok, I asked because you said you added up for each missile.
When I did this problem I succeeded first time with just this standard piece of code
for detecting hits.

[c]
int lefton(point *a, point *b, point *c)
{
return (b->x - a->x)*(c->y - a->y) - (c->x - a->x)*(b->y - a->y) >= 0;
}

int pointinpolygon(point*p, point **P, int n)
{
int i,j;

for (i=0; i<n; i++) {
j = (i + 1) % n;
if (!lefton(P,P[j],p))
return 0;
}
return 1;
}
[/c]

p is the missile position and P is the convex hull of the kingdom.

Hmm.. peculiar.. when I use your angle-code it gets AC, but not with my own. It works with every test I've tried on my own though. Ooh well, thanx for the help.

i think i don't undestand the problem
if missile hits a point
for example 1,1

all power plants in radius 1 will be destroyed??
etc 0,0 ; 0,1 ; 0,2; 1,0;1,1;1,2; 2,0; 2,1 ; 2,2 ???

there's no \n in last line in input of data.
so you'll submission will be WA if you checked with feof(stdin);

all examples i can think of (including the one coming with the problem) are solved correctly. maybe i misunderstood the problem (wouldn't be the first time ) - i still get WA

i'm a bit confused, because the problem states, that the fence is around all houses including the plant. why does the input-description emphasize, that the power plant is the first building given? that shouldn't make any difference, whether the plant is given first or second or whatever...

maybe some of you have some ideas for tricky inputs. i don't know what to change anymore...

thx in advance.

does the example given in the problem look like this?

aahh. i just found something. if the input contains a building twice, my program writes the wrong answer - will investigate in that direction...

nah.

problem fixed, but still WA

these geometrical algorithmic problems are too complicated for me, i'm afraid!

even the simple problem of finding the intersection of 2 segments (which is like solving a set of 2 equations with 2 unkowns) is too hard for me :/ you gotta take take of special cases where the coefficients are zero, etc..

it sucks cause i know this problem is basic.

tets

#109 looked very hard for me as well, but when I started to solve it, it only took me 1.5 hrs (compare to 6 hours I spent for #106(x^2+y^2=z^2)).
In case you want to know how it can be solved:

1:find a city in a kingdom with largest x,

2:find a border (first dot of the border is already found) of a kingdom:
go through all cities - find the city with smallest angle between axle x and vector (last found border dot -> city); (if this angle < angle for last found border dot - increase this angle by 360 before checking if it's the smallest one)

3:find a kingdoms size - sum of triangles (bd[0],bd,bd[i+1]) sizes , where i = [1..n], bd = border dot.

4:find out if a missile hit a kingdom - angles between vectors (bd -> bd[i+1]) and (bd -> missile coordinates) should be all less or equal 180.

The most difficult step is to calculate an angle between two vectors - this angle should be between 0 and 360, but it only takes one arcsin/arccos and 2 ifs.

Good luck.
Probably my English is not good enough to explain algorithms.

I have been struggling with this problem for far too long. My program seems correct but still gets WA.

My program is based around:

[cpp]
inline long triangle_area2x (Point P0, Point P1, Point P2) {
long area;

area = P0.x * (P1.y - P2.y) - P1.x * (P0.y - P2.y) + P2.x * (P0.y - P1.y);

return area;
}
[/cpp]

I use that for calculating kingdom area, building the hull, and detecting bomb hits.

I've actually stooped to finding some code off of the web that gets AC for comparison. I've run thousands of random kingdoms through both programs for comparison. The cases where they do not match, seem to be flaws in the AC program!

Here is a kingdom that seems to trip up the AC program. I would love it if folks with AC solutions could try it out and post their result.
My WA program gets 0.0. The AC program returns 46985.00.

A hand calculation shows that the point 121,96 is outside the kingdom, although it is close to the edge, so 0 is the correct answer. It's closest to the line segment from (371,443)-(114,86). The y value on that line at x=121 is 95.7, below the bomb coord, so the bomb is outside the kingdom.

When I stumble on these problems, it's usually weird inputs that I fail to handle. My prog can handle no final linefeed, duplicate bomb coords and sites and seems to be more tolerant of other screwed up inputs than the AC code. What can I be missing?

Argh!

Iz