每次有三种情况,直线相交判断+dijkstra算法

2020-01-05 19:23 来源:未知

题目链接:pku1066(经典)

题目:pku1556

这道题花了好久的时间才做出来,刚开始没有思路,最后看了网上的解答,好难得样子,每次都没有看完,但是掌握了大概思想,今天试着做了一下,已ac

 

代码一:线段相交+枚举

方法:直线相交判断+dijkstra算法

主要思想:先将点对按照x排序,再在x排好序的基础上按照y来排序,这个用qsort函数就可直接完成,然后主要就是分治法的运用,将点分成小份来寻找最近点对。每次有三种情况,即你分成的两堆点,最近点对的两点都在1.左边那堆  2.右边那堆  3.左边右边各一个,1,2两种情况很好想,主要是第三种情况,关于第三种情况,网上有很多分析有详细说明最少只需要比较6个点即可,我的代码为了方便,我比较了7个点。

//with 1 <= n <= 100000, the number of sticks for this case
//these numbers are the planar coordinates of the endpoints of one stick
// You may assume that there are no more than 1000 top sticks

//0 <= n <= 30  

思路:把每个门的两点看成图中的一个点,构造一个以两点距离为权值的图(如果不可直达,记为INF),

下面是我的代码:

#include<iostream>
#include<cmath>
using namespace std;
struct point
{   double x,y;  };
//计算叉积
double multi(point p0,point p1,point p2)
{   return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}
//判断线段相交
bool is_cross(point s1,point e1,point s2,point e2)
{
   return max(s1.x,e1.x)>=min(s2.x,e2.x)&&
          max(s2.x,e2.x)>=min(s1.x,e1.x)&&
          max(s1.y,e1.y)>=min(s2.y,e2.y)&&
          max(s2.y,e2.y)>=min(s1.y,e1.y)&&
          multi(s2,e1,s1)*multi(e1,e2,s1)>=0&&
          multi(s1,e2,s2)*multi(e2,e1,s2)>=0;
}
#define max 100005
point s[max],e[max];
int main()
{
    long n,i,j,k;
    long ans[1005];
    while(scanf("%ld",&n),n)
    {
        for(i=1;i<=n;i++)
           scanf("%lf%lf%lf%lf",&s[i].x,&s[i].y,&e[i].x,&e[i].y);
        k=1;        
        for(i=n;i>1;i--)
        {  
            for(j=n;j>i;j--)
              if(is_cross(s[i],e[i],s[j],e[j]))break;
            if(j!=i)continue;
            for(j=i-1;j>0;j--)
            {
               if(is_cross(s[i],e[i],s[j],e[j])){ ans[k++]=i; break;}            
            }
            if(j==0)ans[k++]=i;
        }
        for(i=2;i<=n;i++)
           if(is_cross(s[1],e[1],s[i],e[i]))break;
        if(i==n+1)ans[k++]=1;
        printf("Top sticks: %ld",ans[k-1]);
        for(i=k-2;i>0;i--)
          printf(", %ld",ans[i]);
        printf(".n");
    }
    system("pause");
    return 0;
}

#include<iostream>
#include <algorithm>
#include<cmath>
using namespace std;
struct point
{   double x,y;  };
struct line
{   point s, e;  };
double max(double a,double b)
{    return a>b?a:b;        }
double min(double a,double b)
{    return a<b?a:b;        }
//计算叉积
double multi(point p0,point p1,point p2)
{   return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}
//判断线段相交
bool is_cross(point s1,point e1,point s2,point e2)
{
   return max(s1.x,e1.x)>=min(s2.x,e2.x)&&
          max(s2.x,e2.x)>=min(s1.x,e1.x)&&
          max(s1.y,e1.y)>=min(s2.y,e2.y)&&
          max(s2.y,e2.y)>=min(s1.y,e1.y)&&
          multi(s2,e1,s1)*multi(e1,e2,s1)>=0&&
          multi(s1,e2,s2)*multi(e2,e1,s2)>=0;
}
int main()
{
    int n;
    line ss[35];
    point p;
    int i,j,k;
    int node1,node2,min;
    while(cin>>n)
    {
        for(i=0;i<n;i++)
           cin>>ss[i].s.x>>ss[i].s.y>>ss[i].e.x>>ss[i].e.y;
        cin>>p.x>>p.y;min=100;
        for(i=0;i<n;i++)
        {
            node1=0;node2=0;
            for(j=0;j<n;j++)
            {
                if(is_cross(ss[i].s,p,ss[j].s,ss[j].e))node1++;
                if(is_cross(ss[i].e,p,ss[j].s,ss[j].e))node2++;
            }
            if(node1<min)min=node1;
            if(node2<min)min=node2;
        }
        if(n)printf("Number of doors = %dn",min);
        else printf("Number of doors = 1n");
    }
    return 0;
}

再用dijkstra算法求出两个端点点的最短路。

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#define ref 1e20;
#define min(a,b) a>b?b:a;

 

代码二:

注意:不要用memset初始化g,d;用memset初始化为非0值时,其值并非我们想象的,尽管那值很稳定。

typedef struct point {
永利平台娱乐,double x, y;
}Point;

TAG标签:
版权声明:本文由永利平台娱乐发布于新闻动态,转载请注明出处:每次有三种情况,直线相交判断+dijkstra算法