三角形划分
   



  给定三角形内的若干个点,你的任务是找出一种划分三角形的方案,使得这些给定的点被分成三个元素个数相等的子集。(如下图所示)

               

  设三角形的三个顶点分别为A、B和C,给定的N个点为P1,P2,……,Pn。要求你找出一个点Q,使得三个三角形QBC、QCA和QAB包含至少N/3个点。分界线上点将被同时算入两个三角形中。例如在QA上有一个点,则这个点算在三角形QCA内,也算在QAB内。如果Q点恰好是给定点中的一个,则这个点算为同时落在三个三角形内。

  输入

  输入文件包含若干个测试数据,每组数据表示一个数据集合,包含给定的点。一组数据以如下格式0给出:

                   

  第一整数n表示点的个数,点Pi的坐标以(xi,yi)形式给出(0≤xi,yi≤1000)。三角形ABC三个顶点是固定的,即A(0, 0), B(1000, 0)和C(0, 1000)。每个给定的点一定落在三角形ABC内部,不会在三条边上。

  每个点PI严格落在三角形ABC内部(且不在边上)。任何两个点Pi、Pj的连线不过A、B、C中的任一顶点。

  文件的以 n为0表示结束。

  输出

  对于每组数据,输出Q的坐标,格式如样例。(坐标以四位小数形式输出)

  Sample Input

  3
  100 500
  200 500
  300 500
  6
  100 300
  100 600
  200 100
  200 700
  500 100
  600 300
  0

  Sample Output

  166.6667 555.5556
  333.3333 333.3333

  (注:解可能不是唯一,只输出其中一个即可)。

   

 
网站导航 | 关于曙光 | 联系我们 | 请提意见
Copyright © FuJian Sunshine Educational Info. Co.,Ltd.
福建曙光教育资讯有限公司 版权所有