朴素做法是 O(n3) 的,超时。我的做法是枚举每个点,然后求其它点和它连线的斜率,再排序。这样就得到经过该点的直线最多能经过几个点。求个最大值就行了。复杂度是 O(n2logn) 的。把排序换成 hash,可以优化到 O(n2)。

/*************************************************************************
Author: WHU_GCC
Created Time: 2007-8-21 18:58:04
File Name: pku1118.cpp
Description: 
***********************************************************************
*/

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

#define out(x) (cout << #x << ": " << x << endl)
typedef 
long long int64;
const int maxint = 0x7FFFFFFF;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template 
<class T> void show(T a, int n) for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
template 
<class T> void show(T a, int r, int l) for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }

const int maxn = 1000;

typedef 
struct point_t
{
    
int x, y;
}
;

bool d_equal(const double &a, const double &b)
{
    
return abs(a - b) < 1e-9;
}


point_t p[maxn];
int n;

double slope[maxn];
int m;

int main()
{
    
while (scanf("%d"&n), n != 0)
    
{
        
for (int i = 0; i < n; i++)
            scanf(
"%d%d"&p[i].x, &p[i].y);
        
        
int ans = 0;
        
for (int i = 0; i < n; i++)
        
{
            m 
= 0;
            
for (int j = 0; j < n; j++if (i != j)
                slope[m
++= double(p[j].y - p[i].y) / (p[j].x - p[i].x);
            sort(slope, slope 
+ m);
            
int cnt = 1;
            
for (int j = 1; j < m; j++)
            
{
                
if (d_equal(slope[j], slope[j - 1]))
                    cnt
++;
                
else
                    cnt 
= 1;
                ans 
>?= cnt;
            }

        }

        printf(
"%d\n", ans + 1);
    }

    
return 0;
}
posted on 2007-08-21 20:37 Felicia 阅读(462) 评论(1)  编辑 收藏 引用 所属分类: 计算几何
Comments
  • # re: [计算几何]pku1118
    古月残辉
    Posted @ 2009-06-26 13:53
    e 这题我就是朴素的方法过的,没有超时啊,不过运行了500ms,把你的程序提交了下,有点小错,改了以后是300ms,没有感觉出数量级的差别啊,不过你的Hash方法倒是蛮好的~~你都用的map实现吗?STL会不会太慢啊?  回复  更多评论   

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理