首页 > ACM题库 > HDU-杭电 > HDU 3299-Distant Galaxy-枚举[解题报告]HOJ
2014
03-13

HDU 3299-Distant Galaxy-枚举[解题报告]HOJ

Distant Galaxy

问题描述 :

You are observing a distant galaxy using a telescope above the Astronomy Tower, and you think that a rectangle drawn in that galaxy whose edges are parallel to coordinate axes and contain maximum star systems on its edges has a great deal to do with the mysteries of universe. However you do not have the laptop with you, thus you have written the coordinates of all star systems down on a piece of paper and decide to work out the result later. Can you finish this task?

Contestants

输入:

There are multiple test cases in the input file. Each test case starts with one integer N , (1<=N<=100) , the number of star systems on the telescope. N lines follow, each line consists of two integers: the X and Y coordinates of the K -th planet system. The absolute value of any coordinate is no more than 109 , and you can assume that the planets are arbitrarily distributed in the universe.

N = 0 indicates the end of input file and should not be processed by your program.

输出:

There are multiple test cases in the input file. Each test case starts with one integer N , (1<=N<=100) , the number of star systems on the telescope. N lines follow, each line consists of two integers: the X and Y coordinates of the K -th planet system. The absolute value of any coordinate is no more than 109 , and you can assume that the planets are arbitrarily distributed in the universe.

N = 0 indicates the end of input file and should not be processed by your program.

样例输入:

10 
2 3 
9 2 
7 4 
3 4 
5 7 
1 5 
10 4 
10 6 
11 4 
4 6 
0

样例输出:

Case 1: 7

#include<cstdio>
#include<algorithm>
using namespace std;
struct point
{
    int x,y;
    bool operator < (const point& rhs) const
    {
        return x<rhs.x;
    }
};
const int maxn = 100+10;
point p[maxn];
int n,m,y[maxn],on[maxn],on2[maxn],left[maxn];
int solve()
{
    sort(p,p+n);
    sort(y,y+n);
    m=unique(y,y+n)-y;
    if(m<=2)
        return n;
    int ans=0;
    for(int a=0;a<m;a++)
        for(int b=a+1;b<m;b++)
        {
            int ymin=y[a],ymax=y[b];
            int k=0;
            for(int i=0;i<n;i++)
            {
                if(i==0 || p[i].x!=p[i-1].x)
                {
                    k++;
                    on[k]=on2[k]=0;
                    left[k]=k==0?0:left[k-1]+on2[k-1]-on[k-1];
                }
                if(p[i].y>ymin && p[i].y<ymax)
                    on[k]++;
                if(p[i].y>=ymin && p[i].y<=ymax)
                    on2[k]++;
            }
            if(k<=2)
                return n;
            int M = 0;
            for(int j=1;j<=k;j++)
            {
                ans=max(ans,left[j]+on2[j]+M);
                M=max(M,on[j]-left[j]);
            }
        }
        return ans;
}
int main()
{
    int kcase=0;
    while(scanf("%d",&n)==1 && n)
    {
        for(int i=0;i<n;i++)
        {
            scanf("%d%d",&p[i].x,&p[i].y);
            y[i]=p[i].y;
        }
        printf("Case %d: %d\n",++kcase,solve());
    }
    return 0;
}

 参考:http://blog.csdn.net/liruiiuril/article/details/9204731


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。