## 11016 - Square Counting

Moderator: Board moderators

domino
New poster
Posts: 19
Joined: Thu Dec 25, 2003 6:01 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.
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
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;
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; Y[N] = Y;

cnt = cnt = 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 < cnt) swap(cnt, cnt);
printf("%d %d\n", cnt, cnt);
}

return 0;
}``````

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm