首页 > ACM题库 > HDU-杭电 > HDU 3256-Grid Point Counting-枚举-[解题报告]HOJ
2014
03-13

HDU 3256-Grid Point Counting-枚举-[解题报告]HOJ

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

 http://acm.hdu.edu.cn/showproblem.php?pid=3256

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

 

题意:给定500条线段,以浮点型输入最多4为小数。。。问这些线段覆盖的整数点有多少个。。。。数据保证在-10000<x, y<10000。。。

 

分析:需要判重,所以不能直接做。。。总可能点数达到4*10^8个,所以不可能全部标记。。。因为线段条数不多,范围也很小,可以直接枚举x的坐标标记y坐标被覆盖的个数。。。但如果标记每次都初始化为0的话复杂度4*10^8必然超时,这里有点小技巧就是flag标记值值初始化一次,然后更新为当前的x坐标值即可。。这样就是500*20000的复杂度了。。。

此题还比较变态啊。。。输入的数据由于double精度问题不能直接输入。。。所以只能变换输入方式使得所有值都是精确地整数值。。。 

还有。。大于0和小于0时出现取余是一定要注意分别判断。。。wa了好久啊。。。

用double做死定过不了啊。。。郁闷。。。

 

代码:3000+ms

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

 

参考:http://blog.csdn.net/ggggiqnypgjg/article/details/6721130


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

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