11016 - Square Counting
Moderator: Board moderators
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++;
}
}
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++;
}
}
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;
}