首页 > 专题系列 > Java解POJ > POJ 2606 Rabbit hunt [解题报告] Java
2013
11-11

POJ 2606 Rabbit hunt [解题报告] Java

Rabbit hunt

问题描述 :

A good hunter kills two rabbits with one shot. Of course, it can be easily done since for any two points we can always draw a line containing the both. But killing three or more rabbits in one shot is much more difficult task. To be the best hunter in the world one should be able to kill the maximal possible number of rabbits. Assume that rabbit is a point on the plane with integer x and y coordinates. Having a set of rabbits you are to find the largest number K of rabbits that can be killed with single shot, i.e. maximum number of points lying exactly on the same line. No two rabbits sit at one point.

输入:

An input contains an integer N (2<=N<=200) specifying the number of rabbits. Each of the next N lines in the input contains the x coordinate and the y coordinate (in this order) separated by a space (-1000<=x,y<=1000).

输出:

The output contains the maximal number K of rabbits situated in one line.

样例输入:

6
7 122
8 139
9 156
10 173
11 190
-100 1

样例输出:

5

解题代码:

//* @author: [email protected]
import java.util.*;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  int a=in.nextInt();
  int[] arrx=new int[a];
  int[] arry=new int[a];

  for(int i=0;i< a;i++)
  {
   arrx[i]=in.nextInt();
   arry[i]=in.nextInt();
  }
  int max=0;
  for(int i=0;i< a-2;i++)
  {
   for(int j=i+1;j< a-1;j++)
   {
    int c=0;
    for(int u=j+1;u< a;u++)
    {
     if((arrx[i]-arrx[u])*(arry[i]-arry[j])==(arrx[i]-arrx[j])*(arry[i]-arry[u])) c++;
    }
    if(c>max) max=c;
   }
  }
  System.out.println(max+2);
 }
}

  1. 您没有考虑 树的根节点是负数的情况, 若树的根节点是个很大的负数,那么就要考虑过不过另外一边子树了

  2. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }