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
109 - SCUD Busters
Moderator: Board moderators
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.
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.
data of site 109
there's no \n in last line in input of data.
so you'll submission will be WA if you checked with feof(stdin);
so you'll submission will be WA if you checked with feof(stdin);
[109] i'm stuck
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.
) - i still get WAi'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.
109 SCUD Busters & 137 Polygons
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.
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.
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli
#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.
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.
P109 May Cause Embolism
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
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.
Code: Select all
6
204 108
496 315
447 394
184 96
371 443
114 86
-1
121 96
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