The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

POJ 3512-Incidental Points 要选择合适的算法,否则容易超时

这道题可以算是1118,2780的升级版,因为更容易超时了 O(∩_∩)O~
题目的意思很简单,给你许多点,然后让你求出在同在一条直线上的点最多有多少个。
这道题做了2个小时,开始用了暴搜的方法(那个方法不用考虑斜率不存在的情况),超时了,汗~后来改成计算斜率的方法才过的 方法如下:
单独考虑斜率不存在的情况,把所有的点按照x的大小排序,算出x相同的点最多有多少个,保存到max1里;
然后考虑斜率存在的情况,考虑一个定点,把它和其它直线的斜率都算出来,排序,然后再计算相同的斜率最多有多少个,每个点都这样算一遍,取最大值中的最大值,存在max2中;
最后比较max1和max2+1(注意max2我们是用斜率算的,它代表max2+1个点)取较大值输出即可;

#include<iostream>
#include
<cmath>
#include
<cstdio>
#include
<algorithm>
using namespace std;

struct node {
    
int x;
    
int y;
}
set[1001];

int cmp(const void *a,const void *b)
{

    
struct node*c=(node *)a;
    
struct node*d=(node* )b;
    
return c->x-d->x;
}


char temp[100];
double slope[10001];


int main ()

{

    
int n;
    
int i,j,k;
    
int testcase;
    testcase
=0;
    
int max1;
    
int max2;
    
int pos;
    
int tempmax2;
    
for(testcase=1;;testcase++)
    
{

        pos
=0;
        
while(gets(temp))
        
{

            
if(temp[0]=='-'&&temp[1]=='-')
                
break;
            pos
++;
            sscanf(temp,
"%d%d",&set[pos].x,&set[pos].y);
        }

        n
=pos;
        
if(n==0)
            
break;
        
int tempmax=1;
        max1
=0;
        qsort(
set+1,n,sizeof(set[1]),cmp);
        
for(i=2;i<=n;i++)
        
{
            
if(set[i].x!=set[i-1].x)
                tempmax
=1;
            
else
                tempmax
++;
            
if(tempmax>max1)
                max1
=tempmax;
        }

        max2
=0;
        
for(i=1;i<=n;i++)
        
{
            pos
=0;
            
for(j=1;j<=n;j++)
            
{

                
if(i!=j&&set[i].x!=set[j].x)
                
{
                    pos
++;
                    slope[pos]
=((double)set[j].y-set[i].y)/((double)set[j].x-set[i].x);

                }

            }

            sort(slope
+1,slope+1+pos);
            tempmax
=1;
            
            tempmax2
=0;
            
for(j=2;j<=pos;j++)
            
{
                

                
if(slope[j]!=slope[j-1])
                    tempmax
=1;
                
else
                    tempmax
++;
                
if(tempmax>tempmax2)
                    tempmax2
=tempmax;
            }

            
if(tempmax2>max2)
                max2
=tempmax2;
        }

        
if(max1>max2)
            printf(
"%d. %d\n",testcase,max1);
        
else
            printf(
"%d. %d\n",testcase,max2+1);

        }


    
return 0;
}


posted on 2009-03-21 00:48 abilitytao 阅读(1135) 评论(5)  编辑 收藏 引用

评论

# re: POJ 3512-Incidental Points 要選擇合適的算法,否則容易超時 2009-03-21 14:16 Wisely

這個題目算是影像處理(Image Processing)領域的入門題。解法可參考Huff Transform,此演算法原用來在影像上找出點的位置。知道演算法的話,應該很快就可以把程式寫出來了,其中線的表示方式,可以用theta(角度)來表示,追求程式執行效能的話,可以視你需要的精確度,將cos及sin的值先算出來作成mapping table。  回复  更多评论   

# re: POJ 3512-Incidental Points 要选择合适的算法,否则容易超时[未登录] 2009-03-21 16:08 abilitytao

@Wisely
说得很专业呵 要向你学习才是
对了 你为什么用繁体呢?你是台湾人么?  回复  更多评论   

# re: POJ 3512-Incidental Points 要选择合适的算法,否则容易超时[未登录] 2009-03-21 16:18 abilitytao

@Wisely
对了 我可以和你单独交流一下吗
我的qq是:64076241
  回复  更多评论   

# re: POJ 3512-Incidental Points 要选择合适的算法,否则容易超时 2009-03-21 23:16 megax

最近好多人都喜欢做题?  回复  更多评论   

# re: POJ 3512-Incidental Points 要选择合适的算法,否则容易超时[未登录] 2009-03-21 23:44 abilitytao

@megax
这个。。。因为我还在上大学 所以需要做题提高一下自己的能力 希望您能多给我们这些学生一点指点呵  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理