首页 > ACM题库 > HDU-杭电 > Hdu 1352 I Conduit!-计算几何-[解题报告] C++
2013
12-09

Hdu 1352 I Conduit!-计算几何-[解题报告] C++

I Conduit!

问题描述 :

Irv Kenneth Diggit works for a company that excavates trenches, digs holes and generally tears up people’s yards. Irv’s job is to make sure that no underground pipe or cable is underneath where excavation is planned. He has several different maps, one for each utility company, showing where their conduits lie, and he needs to draw one large, consolidated map combining them all. One approach would be to simply draw each of the smaller maps one at a time onto the large map. However, this often wastes time, not to mention ink for the pen-plotter in the office, since in many cases portions of the conduits overlap with each other (albeit at different depths underground). What Irv wants is a way to determine the minimum number of line segments to draw given all the line segments from the separate maps.

输入:

Input will consist of multiple input sets. Each set will start with a single line containing a positive integer n indicating the total number of line segments from all the smaller maps. Each of the next n lines will contain a description of one segment in the format

x1 y1 x2 y2

where (x1,y1) are the coordinates of one endpoint and (x2,y2) are the coordinates of the other. Coordinate values are floating point values in the range 0…1000 speci.ed to at most two decimal places. The maximum number of line segments will be 10000 and all segments will have non-zero length. Following the last input set there will be a line containing a 0 indicating end of input; it should not be processed.

输出:

For each input set, output on a single line the minimum number of line segments that need to be drawn on the larger, consolidated map.

样例输入:

3
1.0 10.0 3.0 14.0
0.0 0.0 20.0 20.0
10.0 28.0 2.0 12.0
2
0.0 0.0 1.0 1.0
1.0 1.0 2.15 2.15
2
0.0 0.0 1.0 1.0
1.0 1.0 2.15 2.16
0

样例输出:

2
1
2

计算几何,主要是排序问题,其他都很好做……

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<string>
using namespace std;
struct seg
{
    double k,b;
    double x1,y1;
    double x2,y2;
    bool flag;
}an[10002];
int same(double a,double b)
{
    if(fabs(a-b)>1e-8) return 0;
    return 1;
}
bool less(double a,double b)
{
    if(a-b>1e-8) return 0;
    return 1;
}
bool cmp(const seg &a,const seg &b)
{
    if(a.flag!=b.flag) return a.flag<b.flag;
    if(a.flag)
    {
        if(!same(a.k,b.k)) return less(a.k,b.k);
        if(same(a.b,b.b)) return less(a.x1,b.x1);
        return less(a.b,b.b);
    }
    else
    {
        if(!same(a.x1,b.x1)) return less(a.x1,b.x1);
        return less(a.y1,b.y1);
    }
}
double MAX(double a,double b)
{
    if(a-b>1e-10) return a;
    return b;
}
int fun(seg &a,seg &b)
{
    if(a.flag!=b.flag) return 0;
    if(a.flag)
    {
        if(!same(a.k,b.k)) return 0;
        if(!same(a.b,b.b)) return 0;
        if(b.x1-a.x2>1e-8) return 0;
        b.x2=MAX(a.x2,b.x2);
        return 1;
    }
    else
    {
        if(same(a.x1,b.x1))
        {
            if(b.y1-a.y2<1e-8)
            {
                b.y2=MAX(b.y2,a.y2);
                return 1;
            }
        }
        return 0;
    }
}
int main()
{
    int b,c,n,m,i,j;
    double x1,x2,y1,y2;
    bool flag;
    while(cin>>n&&n)
    {
        memset(an,0,sizeof(an));
        for(i=0;i<n;i++)
        {
            cin>>an[i].x1>>an[i].y1>>an[i].x2>>an[i].y2;   
            if(an[i].x1==an[i].x2)
            {
                an[i].flag=0;
                if(an[i].y1>an[i].y2) swap(an[i].y1,an[i].y2);
            }
            else
            {
                an[i].flag=1;
                if(an[i].x1>an[i].x2)
                {
                    swap(an[i].x1,an[i].x2);
                    swap(an[i].y1,an[i].y2);
                }
                an[i].k=(an[i].y2-an[i].y1)/(an[i].x2-an[i].x1);
                an[i].b=an[i].y1-an[i].k*an[i].x1;
            }
        }
        sort(an,an+n,cmp);
        m=1;
        for(i=1;i<n;i++)
        {
            if(!fun(an[i-1],an[i]))
                m++;
        }
        cout<<m<<endl;
    }
    return 0;
}

解题报告转载自:http://www.cnblogs.com/xin-hua/p/3198494.html


  1. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥

  2. bottes vernies blanches

    I appreciate the efforts you men and women place in to share blogs on such sort of matters, it was certainly useful. Keep Posting!

  3. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;