学步园

圈水池

描述

有一个牧场，牧场上有很多个供水装置，现在牧场的主人想要用篱笆把这些供水装置圈起来，以防止不是自己的牲畜来喝水，各个水池都标有各自的坐标，现在要你写一个程序利用最短的篱笆将这些供水装置圈起来！（篱笆足够多，并且长度可变）

输入

第一行输入的是N,代表用N组测试数据（1<=N<=10）
第二行输入的是m,代表本组测试数据共有m个供水装置（3<=m<=100）
接下来m行代表的是各个供水装置的横纵坐标

输出

输出各个篱笆经过各个供水装置的坐标点，并且按照x轴坐标值从小到大输出，如果x轴坐标值相同，再安照y轴坐标值从小到大输出

样例输入

1
4
0 0
1 1
2 3
3 0

样例输出

0 0
2 3
3 0

来源

[张洁烽]原创

上传者

张洁烽

import java.awt.Point;
import java.util.ArrayList;
import java.util.Scanner;

//acm 78
public class CircleGround {

    public
static void main(String[] args) {
   
    CircleGround
c = new CircleGround();
       
c.solution();
    }
   
    public void
solution() {
   
    Scanner in =
new Scanner(System.in);
   
    int groups =
in.nextInt();
   
    for (int i =
0; i < groups; i++) {
          
int size = in.nextInt();
          
//list中存储了所有点
          
PointList pointList = new PointList();
          
//result中存储了结果集
          
ArrayList result = new ArrayList();
          

          
for(int j = 0  ;  j < size
;j++){
       
   
   pointList.insert(in.nextInt(),
in.nextInt());
          
}
          

          
result.add(new
Point(pointList.list.get(0).x,pointList.list.get(0).ylist.get(0)));

          
for(int j = 1; j < pointList.list.size();j++){
       
   
  
if(judge(result.get(result.size()-1).x,
result.get(result.size()-1).y,
       
   
   
   
  
pointList.list.get(j).x, 
pointList.list.get(j).ylist.get(0), pointList, true)){
       
   
   
   result.add(new
Point(pointList.list.get(j).x, 
pointList.list.get(j).ylist.get(0)));
       
   
   }
          
}