2014
03-13

# Grid Point Counting

You have a number of sticks, which are thin enough to be considered as segments on the XY plane.

Your task is simple: count the number of grid points that are covered by at least one segment.

The first line contains a single integer T (T <= 10), the number of test cases.
Each case begins with an integer n (1 <= n <= 500), the number of segments.
Each of the following n lines contains four real numbers x1, y1, x2, y2, denoting a segment (x1,y1)-(x2,y2).
All of x1, y1, x2, y2 will be no larger than 10000 in their absolute values, and will contain at most 4 digits after decimal point.

The first line contains a single integer T (T <= 10), the number of test cases.
Each case begins with an integer n (1 <= n <= 500), the number of segments.
Each of the following n lines contains four real numbers x1, y1, x2, y2, denoting a segment (x1,y1)-(x2,y2).
All of x1, y1, x2, y2 will be no larger than 10000 in their absolute values, and will contain at most 4 digits after decimal point.

2
2
-1 0 1 0
0 1 0 -1
1
1 2 3 4.0001

Case 1: 5
Case 2: 1

2009 宁波网赛题。。此次网赛题难度相当不一般啊。。

#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;

const int M=10010;
const int N=510;
char s[110];
struct Line
{
__int64 x1, y1, x2, y2;
} ll[N], pos;
int n, flag[M*2], ans;

void input(__int64 &a)
{
scanf("%s", &s);
int i, j, len=strlen(s);
a = 0;
i = 0;
if(s[0]=='-')
i++;
for(; i<len && s[i]!='.'; i++)
{
a *= 10;
a += s[i]-'0';
}
for(i++, j=0; i<len; i++, j++)
{
a *= 10;
a += s[i]-'0';
}
while(j<4)
{
a *= 10;
j++;
}
if(s[0]=='-')
a = -a;
}

void cal(int i, Line li)
{
if(li.x1==li.x2)
{
if(li.x1==i*10000)
{
if(li.y1>li.y2)
swap(li.y1, li.y2);
if(li.y1<=0)         //小于0的情况没考虑，这里wa了好久啊。。。
li.y1 = li.y1/10000;
else
li.y1 = li.y1/10000+1;
if(li.y2>=0) //...
li.y2 /= 10000;
else
li.y2 = li.y2/10000-1;
for(int j=li.y1; j<=li.y2; j++)
{
if(flag[j+M]!=i)
{
flag[j+M] = i;
ans++;
}
}
}
return;
}
if(!(li.x1<=i*10000 && i*10000<=li.x2) )
return;
if((i*10000-li.x1)*(li.y2-li.y1)%(li.x2-li.x1)==0)
{
int j = (i*10000-li.x1)*(li.y2-li.y1)/(li.x2-li.x1)+li.y1;
if(j%10000==0)
{
j /= 10000;
if(flag[j+M]!=i)
{
flag[j+M] = i;
ans++;
}
}
}
}

int main()
{
int i, j, cas, cas1;

scanf("%d", &cas);
for(cas1=1; cas1<=cas; cas1++)
{
scanf("%d", &n);
pos.x1 = M*M*10;
pos.x2 = -M*M*10;
for(i=0; i<n; i++)
{
input(ll[i].x1);
input(ll[i].y1);
input(ll[i].x2);
input(ll[i].y2);
if(ll[i].x1 > ll[i].x2)
{
swap(ll[i].x1, ll[i].x2);
swap(ll[i].y1, ll[i].y2);
}
if(ll[i].x1<pos.x1)
pos.x1 = ll[i].x1;
if(ll[i].x2<pos.x1)
pos.x1 = ll[i].x2;
if(ll[i].x1>pos.x2)
pos.x2 = ll[i].x1;
if(ll[i].x2>pos.x2)
pos.x2 = ll[i].x2;
}
for(i=0; i<M*2; i++)
flag[i] = -1000000;
ans = 0;
pos.x1 /= 10000;
pos.x1--; //小于0的时候。。。wa啊。。。
pos.x2 /= 10000;
pos.x2++;
for(i=pos.x1; i<=pos.x2; i++)
{
for(j=0; j<n; j++)
{
cal(i, ll[j]);
}
}
printf("Case %d: %d\n", cas1, ans);
}
return 0;
}

代码：double做的死wa。。

#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <set>
#include <iostream>
using namespace std;

const double eps=0.00005;
int M=10001;
const int N=510;
struct Point
{
double x, y;
};
struct Line
{
Point a, b;
} line[N];
int n, ans, flag[20010];
double xn, xx;

inline double ffabs(double x)
{
if(x<0)
return -x;
return x;
}

void cal(int i, Line li)
{
double ii=i;
if(ffabs(li.a.x-li.b.x)<eps)
{
if(ffabs(li.a.x-ii)<eps)
{
int yn, yx;
if(li.a.y>li.b.y)
swap(li.a, li.b);
if(li.a.y<=0)
yn = li.a.y-eps;
else
yn = li.a.y-eps+1;
if(li.b.y>=0)
yx = li.b.y+eps;
else
yx = li.b.y+eps-1;
for(int j=yn; j<=yx; j++)
{
if(flag[j+M]!=i)
{
ans++;
flag[j+M] = i;
}
}
}
return;
}

double y, y1;
int yn;
if(li.a.x-ii>eps || ii-li.b.x>eps)
return;
y = (i-li.a.x)*(li.b.y-li.a.y)/(li.b.x-li.a.x)+li.a.y;
yn = y;
if(ffabs(y-yn)<0.00000001)
{
if(flag[yn+M]!=i)
{
flag[yn+M] = i;
ans++;
}
}
}

int main()
{
int i, j, cas, cas1;

scanf("%d", &cas);
for(cas1=1; cas1<=cas; cas1++)
{
scanf("%d", &n);
xx = -10010;
xn = 10010;
for(i=0; i<n; i++)
{
scanf("%lf%lf%lf%lf", &line[i].a.x, &line[i].a.y, &line[i].b.x, &line[i].b.y);
if(line[i].a.x>line[i].b.x)
swap(line[i].a, line[i].b); //x从小到大。。。
if(line[i].b.x>xx)
xx = line[i].b.x;
if(line[i].a.x<xn)
xn = line[i].a.x;
}

ans = 0;
for(i=0; i<20010; i++)
flag[i] = -1000000;
for(i=xn-1; i<=xx+1; i++)
{
for(j=0; j<n; j++)
cal(i, line[j]);
}
printf("Case %d: %d\n", cas1, ans);
}

return 0;
}

1. 可以参考算法导论中的时间戳。就是结束访问时间，最后结束的顶点肯定是入度为0的顶点，因为DFS要回溯

2. 换句话说，A[k/2-1]不可能大于两数组合并之后的第k小值，所以我们可以将其抛弃。
应该是，不可能小于合并后的第K小值吧