11016 - Square Counting

[domino]

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

[aminallam]

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

[domino]

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

[sclo]

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.

[aminallam]

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.