poj1118（Lining Up）

http://acm.pku.edu.cn/JudgeOnline/problem?id=1118
【题意简述】在点集中求一条直线，使其经过的点数最多，输出该点数。
【分析】O(n^3)暴力搜索，方法类似福建师范大学的2060（Accept）。

import java.util.*;

import java.io.*;

public class poj_1118{

public static void main(String rgs[]) throws Exception

{

Scanner cin = new Scanner(new BufferedInputStream(System.in));

int i,j,k,n = cin.nextInt();

while(n!=0){

int[] x=new int[n];

int[] y=new int[n];

for(i=0;i<n;i++){

x[i] = cin.nextInt();

y[i] = cin.nextInt();

}

int count,flag,max=2,t1=0,t2=0;

for(i=0;i<n-1;i++){

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

count=2;

// 斜率不存在

if(x[j]-x[i]==0)

flag=1;

// 斜率是0

else if(y[j]-y[i]==0)

flag=2;

else{

flag=3;

t1=y[j]-y[i];

t2=x[j]-x[i];

}

for(k=0;k<n;k++){

if(k!=i && k!=j){

switch(flag){

case 1:if(x[k]-x[i]==0) count++;break;

case 2:if(y[k]-y[i]==0) count++;break;

case 3:if(t1*(x[k]-x[i])==t2*(y[k]-y[i])) count++;break;

}

if(count>max)

max=count;

}

System.out.println(max);

n = cin.nextInt();

}

posted on 2009-09-13 09:54 飞翔天使阅读(699) 评论(0) 编辑收藏所属分类: poj

常用链接

留言簿(1)

随笔分类(146)

随笔档案(147)

文章分类(28)

文章档案(28)

喜欢的Blog

搜索

最新评论

阅读排行榜

评论排行榜


只有注册用户登录后才能发表评论。




网站导航: 博客园 IT新闻知识库 C++博客博问
相关文章: poj1157（LITTLE SHOP OF FLOWERS） poj1396（Simple Arithmetics） poj ACM题型分类 poj1125（Stockbroker Grapevine） poj1835（宇航员） poj1163（The Triangle） poj1118（Lining Up） poj1129（Channel Allocation） poj1016（Numbers That Count） poj1001（Exponentiation）