OJ Board

I know this thread is old but I'm stumped, so what the heck.

I have my program (WA) which to my eyes seems fine. To help figure out what's wrong with it, I found some AC code and have been using it as a black box for comparison.

Seolv problem #1:

WA and AC = 7961.00

Seolv problem #2:

WA = 7961.0, AC = 454.0

The difference is the fourth kingdom. WA says bomb 110,195 is a hit while AC says it's not.

The hull is
100, 101
132, 102
200, 195
101, 223

So there doesn't seem to be any question that 110 195 is inside the walls and thus a hit! This is not the first time the AC program has disagreed with my WA program and my WA has always been right.



cyfra problem:

my WA and the AC I have both get 101.0

seolv claims 100.0 from an AC program.
zbogi claims 0.0 from an AC program.



So this problem is nuts. All these AC programs getting DIFFERENT (and maybe wrong) answers? How can this be? At the very least, the judge test set is not very complete or it would weed some of these so-called ACs out. I'm starting to suspect the judge is flat out wrong but I'm too stubborn to code a bug in just to get AC.

But, then again, my solution is WA, so what do I know. I suspect some devious, tricky input that I haven't thought of.

Iz

My AC'd program prints 0.00 for your input. Make sure your program prints those zeros. If you want a lot of headache I can post my code here.

You can also post your solution here - It helps most of the times.

PS: Your "triangle_area2x" is 3 times shorter than my triangle area function.

Ivan Golubev wrote:Judge is OK for problems 109 and 361. If you have some examples of incorrect datas then post them here.

- I think this is what you should do. Just post your inputs/outputs, minimize them if you know which exactly kingdom/missile cause error.
(I can't check your answers with my program because you did not post inputs)

minskcity wrote:Make sure your program prints those zeros.

Thanks for pointing this out. I was sloppy in my original posting and only typed "0.0". My program does it correctly:

• >./p109 < test.in
  0.00

Sorry if I was not clear where the problem sets came from.

The problems I refer to occur earlier in the thread.

The "Seolv #2" problem came from seolv's post above. Here I've reduced it to the relevant part:

10
100 101
200 195
143 199
111 200
107 154
132 102
101 223
110 155
118 107
102 148
-1
110 195

For this reduced version my WA prog gets 7507.00.
An AC prog I have access to got 0.00.

The "cyfra problem" came from cyfra's post:

4
0 0
1 1
1 0
0 1
4
10 10
20 10
20 20
10 20
-1
1 1
15 10

My WA and the AC code I have both get 101.00, seolf claimed his/her AC got 100.00, and zbogi claimed his/her AC got 0.00. Three AC codes with three different answers!

Iz

My AC'd code gives answers:
Same as your WA program, so this is not the reason you get WA...
From my experience, OJ can accept wrong code, but I've never seen him saying that correct code is wrong. Two more things you should try:

1)Try to allign your code when sending it by e-mail or try to use other e-mail provider.(This caused my correct code to result in WA a couple times)
2)Post your code here - I think you'll have 95% chance to find your mistakes(if there are any, see (1)).

PS: If you have more inputs you would like to check post them here.
Good luck.

Tried a couple of email servers. No difference. Made sure I wasn't using any C++ style comments. Pre-wrapped my source to 72 chars/line before mailing. Still WA. Matched over 7000 random kingdoms vs. AC code and then the AC prog messed up. Compiled on a x86 linux box which ought to be more "Judge-like" and saw no difference. Beats me what the Judge doesn't like.

Post your code here

Well, here it is, in all of it's verbose glory.

[cpp]
/* @BEGIN_OF_SOURCE_CODE */

/* @JUDGE_ID: ####### 109 C++ */

#include <iostream>
#include <iomanip.h>

using namespace std;

const unsigned long MaxKingdoms = 20;
const unsigned long MaxSites = 100;
const long MaxCoord = 500;
const long MinCoord = 0;

class Point {
public:
long x;
long y;
};

/*
-- Calculate 2*area of the triangle formed by P0P1P2. Area will be
-- positive if points are anticlockwise. Positive if clockwise.
-- Zero if colinear.
*/
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;
}

class Kingdom {
public:
Kingdom () {
numSites = 0;
numHullPoints = 0;
minSiteIndex = -1;
minSite_y = MaxCoord + 1;
Bombed = false;
}

inline void AddPoint(long x, long y) {
/*
-- Make sure site not already present.
*/
for (long index = 0; index < numSites; index++) {
if ( sites[index].x == x && sites[index].y == y ) {
return;
}
}

sites[ numSites ].x = x;
sites[ numSites ].y = y;
if ( minSite_y > y) {
minSiteIndex = numSites;
minSite_y = y;
}
numSites++;
}

inline void FindHull(void) {
long hullindex;
long tri_area;
Point hullpoint;
long index;

for (index = 0; index < numSites; index++) {
hull[index] = sites[index];
}

/*
-- determine the convex hull that contains all of the sites
-- in a kingdom
*/
hullpoint = hull[minSiteIndex];
hull[minSiteIndex] = hull[0];
hull[0] = hullpoint;

numHullPoints = 1;

while (numHullPoints <= numSites) {
hullindex = (numHullPoints > 1) ? 0 : 1;

for (index = numHullPoints; index < numSites; index++) {
tri_area = triangle_area2x(hull[numHullPoints-1],
hull[hullindex], hull[index]);

if (tri_area < 0) {
/*
-- negative area, the new point can see the
-- provisional edge, so make it
-- the new hullpoint
*/
hullindex = index;
}
}


/*
-- If the hull point is the minSite, then we're done.
*/
hullpoint = hull[hullindex];

if ( (hullpoint.x == hull[0].x) &&
(hullpoint.y == hull[0].y) )
{
break;
}

/*
-- add the hullpoint to the hull and update area
*/
hull[hullindex] = hull[numHullPoints];
hull[numHullPoints] = hullpoint;
numHullPoints++;
}
}

inline bool isBombed(void) {
return Bombed;
}

inline void Bomb(long x, long y) {
Point p;
long area;

if (Bombed) {
return;
}

p.x = x;
p.y = y;

/*
-- Walk the hull. If p is outside any hull edge then the
-- bomb missed.
*/
long hullindex;
for (hullindex = 0; hullindex < numHullPoints; hullindex++)
{
area = triangle_area2x(hull[hullindex],
hull[(hullindex+1) % numHullPoints], p);
if (area < 0) {
Bombed = false;
return;
}
}

Bombed = true;
}

inline float GetArea(void) {

long index;
float slice_area;
float area;

area = 0.0;

for (index=1;index < numHullPoints - 1; index++) {
slice_area = (0.5) * (float)triangle_area2x(hull[0],
hull[index], hull[index+1]);
area += slice_area;
}

return area;
}

private:
long numSites;
long numHullPoints;
long minSiteIndex;
long minSite_y;
Point sites[MaxSites];
Point hull[MaxSites];

bool Bombed;
};

Kingdom kingdoms[MaxKingdoms];

int main(void)
{
long SitesInKingdom;
long index;
long x, y;
float area;
long numkingdoms;

cout.setf(ios::fixed, ios::floatfield);
cout.precision(2);

numkingdoms = 0;

/*
-- read in sites for all kingdoms
*/
for(;;) {
cin >> SitesInKingdom;
if (cin.eof() || (SitesInKingdom == -1)) {
break;
}

for ( index = 0; index < SitesInKingdom; index++ ) {
cin >> x >> y;
if (cin.eof()) {
break;
}
kingdoms[numkingdoms].AddPoint(x,y);
}

kingdoms[numkingdoms].FindHull();

numkingdoms++;
}

/*
-- Read in bombing coords
*/
while (cin >> x >> y) {
for ( index = 0; index < numkingdoms; index++ ) {
kingdoms[index].Bomb(x,y);
}
}

/*
-- Find area of all bombed kingdoms
*/
area = 0.0;

for ( index = 0; index < numkingdoms; index++ ) {
if ( kingdoms[index].isBombed() ) {
area += kingdoms[index].GetArea();
}
}

cout << area << endl;
}

/* @END_OF_SOURCE_CODE */

[/cpp]

I appreciate any ideas.

I've run 1.000.000 samples, 4 kingdoms each (500mb) my solution vs yours, only 1 different answer, your solution's answer was correct. Now I'm upgrating my input generator to produce more "difficult" inputs, such as lots of sites&missiles on borders, missiles with the same coordinates, kingdoms with common borders, as many kingdoms and sites as possible. I'll post my results in tomorrow.

In case you want one more AC'd solution:

[cpp]#include <iostream.h>
#include <stdio.h>
#include <math.h>
#include <conio.h>
const double PI = 3.14159;

struct my_2d{
int x,y;
};

struct my_kingdom{
double size;
int wall_count;
my_2d wall[100];
char striked;
};

void culc_size(my_kingdom &kingdom){
kingdom.size = 0;
double a,b,c,ax,bx,cx,ay,by,cy,p;
for(int i = 2; i < kingdom.wall_count; i++){
ax = kingdom.wall[0].x - kingdom.wall[i-1].x;
ay = kingdom.wall[0].y - kingdom.wall[i-1].y;
bx = kingdom.wall[0].x - kingdom.wall.x;
by = kingdom.wall[0].y - kingdom.wall.y;
cx = kingdom.wall[i-1].x - kingdom.wall.x;
cy = kingdom.wall[i-1].y - kingdom.wall.y;
a = sqrt(ax*ax + ay*ay);
b = sqrt(bx*bx + by*by);
c = sqrt(cx*cx + cy*cy);
p = (a + b + c)/2;
kingdom.size += sqrt(p*(p - a)*(p - b)*(p - c));
}
}

double angle(int x, int y){
double out = asin(y/sqrt(x*x+y*y));
if((x >= 0)&&(y < 0)) out = 2 * PI + out;
if(x < 0) out = PI - out;
return out;
}

char damaged(double x, double y, my_kingdom kingdom){
double wall_angle,missile_angle;
int i;
for(i = 0; i < (kingdom.wall_count - 1); i++){
if((x == kingdom.wall.x) && (y == kingdom.wall.y)) return 1;
wall_angle = angle(kingdom.wall[i+1].x - kingdom.wall.x,kingdom.wall[i+1].y - kingdom.wall.y);
missile_angle = angle(x - kingdom.wall.x,y - kingdom.wall.y);
if(missile_angle < wall_angle) missile_angle += 2*PI;
if(missile_angle - wall_angle > PI) return 0;
}

if((x == kingdom.wall[i].x) && (y == kingdom.wall[i].y)) return 1;
wall_angle = angle(kingdom.wall[0].x - kingdom.wall[i].x,kingdom.wall[0].y - kingdom.wall[i].y);
missile_angle = angle(x - kingdom.wall[i].x,y - kingdom.wall[i].y);
if(missile_angle < wall_angle) missile_angle += 2*PI;
if(missile_angle - wall_angle > PI) return 0;

return 1;
}

my_kingdom kingdom[20];
my_2d temp[100];

int main(){
cout.setf(ios::fixed, ios::floatfield);
cout.precision(2);
int n,max,max_ind,now_ind,min_ind,kingdom_num;
double now_angle,temp_angle,min_angle,answer;

for(int i = 0; i < 20; i++) kingdom[i].striked = 0;
kingdom_num = 0;
do{
cin >> n;
if(n!=-1){
for(int i = 0; i < n; i++) cin >> temp[i].x >> temp[i].y;
max = 0;
for(int i = 0; i < n; i++)
if(max < temp[i].x){
max = temp[i].x;
max_ind = i;
}
now_angle = 0;
kingdom[kingdom_num].wall_count = 0;
now_ind = max_ind;

do{
min_angle = 4*PI;
for(int i = 0; i < n; i++)
if(now_ind != i){
if((temp[i].x - temp[now_ind].x == 0) && (temp[i].y - temp[now_ind].y == 0)) continue ;
temp_angle = angle(temp[i].x - temp[now_ind].x,temp[i].y - temp[now_ind].y);
if(temp_angle < now_angle) temp_angle += 2*PI;
if(temp_angle < min_angle){
min_angle = temp_angle;
min_ind = i;
}
}

kingdom[kingdom_num].wall[kingdom[kingdom_num].wall_count].x = temp[min_ind].x;
kingdom[kingdom_num].wall[kingdom[kingdom_num].wall_count].y = temp[min_ind].y;
kingdom[kingdom_num].wall_count++;
now_ind = min_ind;
now_angle = min_angle;

}while(now_ind != max_ind);
}
kingdom_num++;
}while(n != -1);
kingdom_num--;

for(int i = 0; i < kingdom_num; i++) culc_size(kingdom[i]);

int x,y;
answer = 0;
while(cin >> x >> y){
if((x == -2)&&(y == -2)) break;
if((x == -3)&&(y == -3)) break;
for(int i = 0; i < kingdom_num; i++)
if(damaged(x,y,kingdom[i])) kingdom[i].striked = 1;
}

for(int i = 0; i < kingdom_num; i++)
if(kingdom[i].striked) answer += kingdom[i].size;

cout << answer << endl;
getch();
return 0;
}[/cpp]

PS: your solution is 4 times faster than mine.

3.000.000 more inputs tested, 1 more bug found (I don't know weather it's in my code of yours)

input: my answer: your answer: just one missile, so mistake is in one of ours kingdom area culculations.
That's it for me for today, I'm going to job.

Last minutes before my work.....

input: your answer: Could you explain me how kingdom area can increase after removing two sites from the kingdom??

minskcity, you've been very, very helpful!

Your AC solution is much more robust than the one I found on the web.

The bug is in my program. It is not handling the colinear points (498,9), (498,91), and (498,312) properly. It gets confused and leaves (498,312) outside the hull.

When you deleted two points -- I think you deleted the first two (480,313)
and (498,91). That eliminated one of the colinear points and my prog then put (498,312) on the hull and thus the area increased.

I fixed that and now I get AC.

Thanks!

No problem. While reading your code I found out for myself:

1)How to print a number with (and correct to) two decimal places using cout (I used printf before I saw you code).

2)How to calculate triangle area without floats and sqrt().

3)That it's possible to solve this problem only using integers (My code have lots of potential errors caused by float precision and sin/sqrt).

By the way, what did you use "iomanip.h" for? Do you know that compiler ignores

[quote]By the way, what did you use "iomanip.h" for? Do you know that compiler ignores

I have tried to solve prob 109 several times, but I always get WA.

this is my source code :

[cpp]#include <iostream>
#include <vector>
#include <iomanip>
#include <cmath>

using namespace std;

struct Point {
int x;
int y;
};

struct Kingdom {
int N;
Point p[100];
vector<int> CH;
bool Destroyed;
};

bool hit(Kingdom K, Point P);
double calcArea(Kingdom K);
vector<int> makeConvexHull(Point* p, int N);
int direction (Point x, Point y, Point z);

int main()
{
int N, TK = 0;
double Area = 0;
Point* p;
Kingdom K[20];

cin >> N;
while (N != -1) {
K[TK].N = N;
for (int i = 0; i < N; i++) {
cin >> K[TK].p.x >> K[TK].p.y;
}

K[TK].CH = makeConvexHull(K[TK].p, N);

/*if (K[TK].CH[0] == 0)
K[TK].Destroyed = true;
else*/
K[TK].Destroyed = false;

cin >> N;
TK++;
}

Point M;
while ((cin >> M.x >> M.y)) {
for (int i = 0; i < TK; i++) {
if (!K.Destroyed && hit(K, M)) {
Area += calcArea(K);
K.Destroyed = true;
}
}
}

cout << setiosflags(ios::fixed) << setprecision(2) << Area << endl;
}

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;
}

bool hit(Kingdom K, Point P)
{
int OldDirection = 0, NewDirection;
for (int i = 0; i < K.CH.size() - 1; i++) {
if (!lefton(K.p[K.CH], K.p[K.CH[i + 1]], P))
return false;
/*
NewDirection = direction(K.p[K.CH], K.p[K.CH[i + 1]], P);

if (NewDirection == 0)
continue;

if (OldDirection == 0)
OldDirection = NewDirection;

if (OldDirection != NewDirection)
return false; */
}

return true;
}

double calcArea(Kingdom K)
{
double Result = 0;
for (int i = 1; i < K.CH.size() - 1; i++) {
Result += abs(K.p[K.CH[0]].x * K.p[K.CH].y
+ K.p[K.CH].x * K.p[K.CH[i + 1]].y
+ K.p[K.CH[i + 1]].x * K.p[K.CH[0]].y
- K.p[K.CH[i]].x * K.p[K.CH[0]].y
- K.p[K.CH[i + 1]].x * K.p[K.CH[i]].y
- K.p[K.CH[0]].x * K.p[K.CH[i + 1]].y);
}

return (Result / 2);
}

vector<int> makeConvexHull(Point* p, int N)
{
int ld, nd, lp;
vector<int> r;

lp = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (lp == j) continue;

ld = 0;
for (int k = 0; k < N; k++) {
nd = direction(p[i], p[j], p[k]);

if (ld == 0)
ld = nd;
else if (nd != 0 && nd != ld)
break;
}

if (ld != 0 && (ld == nd || nd == 0)) {
r.push_back(i);
lp = i;
i = j - 1;
break;
}
}

if (r.size() > 1 && r[0] == r[r.size() - 1])
break;
}

return r;
}

int direction(Point x, Point y, Point z)
{
int t = x.x * y.y + y.x * z.y + z.x * x.y
- x.y * y.x - y.y * z.x - z.y * x.x;

if (t > 0)
return 1;
else if (t < 0)
return -1;
else
return 0;
}
[/cpp]

I heard that there are no test case which missile lands wall of convex.
(So each AC prog makes different answers)

Why my code get WA from judge?

I have tried to solve prob 109 several times, but I always get WA.

this is my source code :

[cpp]#include <iostream>
#include <vector>
#include <iomanip>
#include <cmath>

using namespace std;

struct Point {
int x;
int y;
};

struct Kingdom {
int N;
Point p[100];
vector<int> CH;
bool Destroyed;
};

bool hit(Kingdom K, Point P);
double calcArea(Kingdom K);
vector<int> makeConvexHull(Point* p, int N);
int direction (Point x, Point y, Point z);

int main()
{
int N, TK = 0;
double Area = 0;
Point* p;
Kingdom K[20];

cin >> N;
while (N != -1) {
K[TK].N = N;
for (int i = 0; i < N; i++) {
cin >> K[TK].p.x >> K[TK].p.y;
}

K[TK].CH = makeConvexHull(K[TK].p, N);

K[TK].Destroyed = false;

cin >> N;
TK++;
}

Point M;
while ((cin >> M.x >> M.y)) {
for (int i = 0; i < TK; i++) {
if (!K.Destroyed && hit(K, M)) {
Area += calcArea(K);
K.Destroyed = true;
}
}
}

cout << setiosflags(ios::fixed) << setprecision(2) << Area << endl;
}

bool hit(Kingdom K, Point P)
{
int OldDirection = 0, NewDirection;
for (int i = 0; i < K.CH.size() - 1; i++) {
NewDirection = direction(K.p[K.CH], K.p[K.CH[i + 1]], P);

if (NewDirection == 0)
continue;

if (OldDirection == 0)
OldDirection = NewDirection;

if (OldDirection != NewDirection)
return false;
}

return true;
}

double calcArea(Kingdom K)
{
double Result = 0;
for (int i = 1; i < K.CH.size() - 1; i++) {
Result += abs(K.p[K.CH[0]].x * K.p[K.CH].y
+ K.p[K.CH].x * K.p[K.CH[i + 1]].y
+ K.p[K.CH[i + 1]].x * K.p[K.CH[0]].y
- K.p[K.CH].x * K.p[K.CH[0]].y
- K.p[K.CH[i + 1]].x * K.p[K.CH[i]].y
- K.p[K.CH[0]].x * K.p[K.CH[i + 1]].y);
}

return (Result / 2);
}

vector<int> makeConvexHull(Point* p, int N)
{
int ld, nd, lp;
vector<int> r;

lp = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (lp == j) continue;

ld = 0;
for (int k = 0; k < N; k++) {
nd = direction(p[i], p[j], p[k]);

if (ld == 0)
ld = nd;
else if (nd != 0 && nd != ld)
break;
}

if (ld != 0 && (ld == nd || nd == 0)) {
r.push_back(i);
lp = i;
i = j - 1;
break;
}
}

if (r.size() > 1 && r[0] == r[r.size() - 1])
break;
}

return r;
}

int direction(Point x, Point y, Point z)
{
int t = x.x * y.y + y.x * z.y + z.x * x.y
- x.y * y.x - y.y * z.x - z.y * x.x;

if (t > 0)
return 1;
else if (t < 0)
return -1;
else
return 0;
}
[/cpp]

I heard that there are no test case which missile lands wall of convex.
(So each AC prog makes different answers)

Why my code get WA from judge?