OJ Board

Posted: **Sun Apr 02, 2006 6:51 pm**

I would really appreciate some test cases. I can't figure out why I keep getting WA.

Posted: **Sun Apr 02, 2006 9:25 pm**

I am not good at designing test cases, but this may help:
If you did not make these:
1) Ignore horizontal edges.
2) At each y, Compute edge intersection with the line Y=y, Y=y+1. Let the x cords xl, xr (where xl min of them, xr max). Edges are sorted by xl, and in tie by xr. xl, xr are double precision. The following code computes all included cells in this row:

int prev=-1;
for(it=cur_edges.begin(); it!=cur_edges.end(); it++)
{
Edge& e1 = edges[*it]; it++;
Edge& e2 = edges[*it];

int num = max(0, floor(e2.xl)-ceil(e1.xr));
sum1 += num/2;
sum2 += num/2;

if(num%2==1){
int poo = floor(e2.xl)+y;
if(poo%2) sum1++; else sum2++;
}
}

Posted: **Sun Apr 02, 2006 11:40 pm**

I don't get it, I do it exactly like you explained. Here is my code:

Code: Select all

#include <stdio.h>
#include <math.h>
#include <algorithm>

using namespace std;

#define MAX_N 105
#define EPS 1e-9
#define FOR(i, a, b) for (i = (a); i < (b); i++)
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define pb push_back
#define mp make_pair
#define less_eq(a, b) ((a) < (b)+EPS)
#define f first
#define s second

int N, X[MAX_N], Y[MAX_N], ne, cnt[2];
pair <double, double> E[MAX_N<<1];

int main(void)
{
    int x, i, l, r;
    double y1, y2, t;

    for (; scanf("%d", &N) == 1 && N; )
    {
        FOR (i, 0, N) scanf("%d %d", X+i, Y+i);
        X[N] = X[0]; Y[N] = Y[0];

        cnt[0] = cnt[1] = 0;
        FOR (x, 0, 10001)
        {
            ne = 0;
            FOR (i, 0, N)
            {
                if (X[i] == X[i+1]) continue;

                y1 = y2 = 1e13;
                t = (double)(x-X[i])/(double)(X[i+1]-X[i]);
                if (less_eq(0.0, t) && less_eq(t, 1.0))
                    y1 = Y[i] + (Y[i+1]-Y[i])*t;
                t = (double)(x+1-X[i])/(double)(X[i+1]-X[i]);
                if (less_eq(0.0, t) && less_eq(t, 1.0))
                    y2 = Y[i] + (Y[i+1]-Y[i])*t;
                if (y1 == 1e13 || y2 == 1e13) continue;

                if (y1 > y2) swap(y1, y2);
                E[ne++] = mp(y1, y2);
            }
            sort(E, E+ne);

            for (i = 0; i+1 < ne; i += 2)
            {
                l = (int) ceil(E[i].s);
                r = (int) floor(E[i+1].f);
                if (l >= r) continue;
                cnt[(x+l)&1] += (r-l)/2;
                cnt[!((x+l)&1)] += (r-l) - (r-l)/2;
            }
        }

        if (cnt[0] < cnt[1]) swap(cnt[0], cnt[1]);
        printf("%d %d\n", cnt[0], cnt[1]);
    }

    return 0;
}

Posted: **Mon Apr 03, 2006 3:18 am**

This problem can be solved without using any floating point arithmetic. So try to do every calculations as integers. It's possible to have precision error if we use double or floats.

Posted: **Fri Apr 14, 2006 7:00 pm**

These two questions are not related:
1) I would like to know how to make it using integers.
2) I will make a lot benefit from sweeping if there is a math formula to get number of grid squares inside a trapezoid with two edges parallel to x-axis.

OJ Board

11016 - Square Counting