首页 > ACM题库 > HDU-杭电 > Hdu 1687 Lucky Light-解析几何[解题报告] C++
2013
12-21

Hdu 1687 Lucky Light-解析几何[解题报告] C++

Lucky Light

问题描述 :

We have a (point) light source at position (xL, yL) with yL > 0, and a finite series of line segments, all of finite non-zero length, given by the coordinates of their two endpoints. These endpoints are all different. The line segments are all situated above the x-axis (y > 0).The segments cast their shadows onto the x-axis. We assume that the shadows of two segments either do not overlap at all, or have an overlap that has some non-zero width (they do not just touch). We also assume that for each segment its shadow is more than just one point, i.e., there is no segment that is directed toward the light source. The height of the light source (yL) is at least 1 unit larger than the y-coordinates of the endpoints of the line segments. This guarantees that indeed each line segment has a bounded shadow on the x-axis.

The collection of shadows divides the x-axis into dark and lighted areas (intervals). The problem is to determine the number of lighted areas ― which is at least 2 (if there is at least one line segment, otherwise it is 1).

In the picture below the three line segments A, B and C cause three lighted areas, as indicated.

输入:

The first line of the input file contains a single number: the number of test cases to follow. Each test case has the following format:One line with one integer n with 0 ≤ n ≤ 100: the number of line segments.
One line with two integers xL and yL, the coordinates of the light source, separated by a single space. The coordinates satisfy -100 ≤ xL ≤ 100 and 1 ≤ yL ≤ 1,000.
n lines, each containing four integers xi, yi, ui and vi, separated by single spaces, that specify x- and y-coordinates of the two endpoints (xi, yi) and (ui, vi) of the ith line segment, where -100 ≤ xi, ui ≤ 100 and 0 < yi, vi < yL, for 1 ≤ i ≤ n.

输出:

For every test case in the input file, the output should contain a single number, on a single line: the number of lighted areas.

样例输入:

2
3
50 60
55 45 30 35
64 39 92 18
20 30 40 16
2
-10 50
-10 1 10 11
-10 11 10 1

样例输出:

3
2


敲打代码的时候竟然忘记qsort()怎么用的了……

题目大致意思就是求线段投影把x轴分成几段了,之前看过一道例题(刘汝佳编写的《算法入门经典》提到过类似的题目,有类似的思路吧),很类似……

#include "stdio.h"
#include "stdlib.h"
#include "math.h"

typedef struct point{
    double start,end;
}points;

points p[120];
int s_x,s_y;

double get_x(int x,int y)
{
    if(x==s_x)
        return (double)x;
    else
        return (double)(y*s_x-s_y*x)/(double)(y-s_y);
}

int cmp(const void *p1,const void *p2)
{
 return ((*(points *)p1).end)>((*(points *)p2).end)?1:-1;
}

int main()
{
    int T;
    int n;
    int count,k,i,j;
    int x_s,x_e,y_s,y_e;
    double x1,x2,last;
    scanf("%d",&T);

    while(T--)
    {
        scanf("%d",&n);
        scanf("%d%d",&s_x,&s_y);
        for(i=0;i<n;i++)
        {
            scanf("%d%d%d%d",&x_s,&y_s,&x_e,&y_e);
            x1=get_x(x_s,y_s);
            x2=get_x(x_e,y_e);
            if(x1<x2)
            {
                p[i].start=x1;
                p[i].end=x2;
            }
            else
            {
                p[i].start=x2;
                p[i].end=x1;
            }
        }
        qsort(p,n,sizeof(points),cmp);
        /*for(i=0;i<n;i++)
        {
            for(j=0;j<n-i-1;j++)
            {
                if(p[j].end>p[j+1].end)
                {
                    temp=p[j].end;
                    p[j].end=p[j+1].end;
                    p[j+1].end=temp;
                    temp=p[j].start;
                    p[j].start=p[j+1].start;
                    p[j+1].start=temp;
                }
            }
        }*/

        k=0;
        count=0;
        for(i=0;i<n&&k<n;i++)
        {
            last=p[k].end;
            for(j=k+1;j<n;j++)
            {
                if(p[j].start<last)
                {
                    last=p[j].end;
                    k=j;
                }
            }
                k++;
                count++;
        }

        printf("%d\n",count+1);
    }

    return 0;
}

转自:http://www.cnblogs.com/Shirlies/archive/2012/02/11/2347040.html


  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  2. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。