H - Highways

题目链接：

题目：

Flatopia岛国完全平坦。不幸的是，Flatopia的公共高速公路系统非常糟糕。弗拉托利亚政府意识到了这个问题，并且已经建造了一些连接一些最重要城镇的高速公路。但是，仍有一些城镇无法通过高速公路抵达。有必要建造更多的高速公路，以便能够在不离开高速公路系统的情况下在任何一对城镇之间行驶。

    Flatopian城镇的编号从1到N，城镇i的位置由笛卡尔坐标（xi，yi）给出。每条高速公路连接两个城镇。所有高速公路（原始高速公路和要建造的高速公路）都遵循直线，因此它们的长度等于城镇之间的笛卡尔距离。所有高速公路都可以在两个方向使用。高速公路可以自由地相互交叉，但司机只能在位于两条高速公路尽头的小镇的高速公路之间切换。

    Flatopian政府希望最大限度地降低建设新高速公路的成本。但是，他们希望保证每个城镇都可以从其他城镇到达公路。由于Flatopia是如此平坦，高速公路的成本总是与其长度成正比。因此，最便宜的高速公路系统将是最小化总公路长度的系统。

输入

    输入包括两部分。第一部分描述了该国的所有城镇，第二部分描述了所有已建成的高速公路。

    输入文件的第一行包含一个整数N（1 <= N <= 750），表示城镇数量。接下来的N行每行包含两个整数，xi和yi由空格分隔。这些值给出了第i个城镇的坐标（对于i从1到N）。坐标的绝对值不超过10000.每个城镇都有一个独特的位置。

    下一行包含单个整数M（0 <= M <= 1000），表示现有高速公路的数量。接下来的M行每行包含一对由空格分隔的整数。这两个整数给出了一对已经通过高速公路连接的城镇号码。每对城镇至少由一条高速公路连接。

产量

    为每条新高速公路写一条输出线，以便连接所有城镇，尽可能减少新高速公路的总长度。每条高速公路都应该通过打印这条高速公路连接的城镇号码来展示，并以空间隔开。

    如果不需要建立新的高速公路（所有城镇都已连接），则应创建输出文件，但应该为空。

样本输入

    9

    1 5

    0 0

    3 2

    4 5

    5 1

    0 4

    5 2

    1 2

    5 3

    3

    1 3

    9 7

    1 2

样本输出

    1 6

    3 7

    4 9

    5 7

    8 3

思路:先求出两个点之间的距离存起来，然后给出的M个高速公路合并，然后遍历整个城镇，把祖先不同的输出即可，注意下标，城镇编号是从1开始的

 

//// Created by hanyu on 2019/7/31.//#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include
           
            using namespace std;typedef long long ll;const int maxn=2e7+7;int father[maxn];double x[maxn],y[maxn];struct Node{ int u,v; double w; bool operator<(const Node &other)const{ return this->w