11016 - Square Counting

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

domino
New poster
Posts: 19
Joined: Thu Dec 25, 2003 6:01 pm

Post by domino » Sun Apr 02, 2006 6:51 pm

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

aminallam
New poster
Posts: 39
Joined: Thu Dec 08, 2005 12:51 pm
Location: Suez, Egypt.

Post by aminallam » 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++;
}
}

domino
New poster
Posts: 19
Joined: Thu Dec 25, 2003 6:01 pm

Post by domino » 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;
}

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » 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.

aminallam
New poster
Posts: 39
Joined: Thu Dec 08, 2005 12:51 pm
Location: Suez, Egypt.

Post by aminallam » 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.

Post Reply

Return to “Volume 110 (11000-11099)”