1610: [Usaco2008 Feb]Line连线游戏
2024-10-02 07:55:57
1610: [Usaco2008 Feb]Line连线游戏
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 1396 Solved: 615
[Submit][Status]
Description
Farmer John最近发明了一个游戏,来考验自命不凡的贝茜。游戏开始的时 候,FJ会给贝茜一块画着N (2 <= N <= 200)个不重合的点的木板,其中第i个点 的横、纵坐标分别为X_i和Y_i (-1,000 <= X_i <=1,000; -1,000 <= Y_i <= 1,000)。 贝茜可以选两个点画一条过它们的直线,当且仅当平面上不存在与画出直线 平行的直线。游戏结束时贝茜的得分,就是她画出的直线的总条数。为了在游戏 中胜出,贝茜找到了你,希望你帮她计算一下最大可能得分。
Input
* 第1行: 输入1个正整数:N
* 第2..N+1行: 第i+1行用2个用空格隔开的整数X_i、Y_i,描述了点i的坐标
Output
第1行: 输出1个整数,表示贝茜的最大得分,即她能画出的互不平行的直线数
Sample Input
4
-1 1
-2 0
0 0
1 1
Sample Output
* 第1行: 输出1个整数,表示贝茜的最大得分,即她能画出的互不平行的直线数
HINT
4 输出说明: 贝茜能画出以下4种斜率的直线:-1,0,1/3以及1。
Source
没啥好说的:直接求出所有斜率然后排序(特别注意斜率为正无穷,或者说是斜率不存在的情况)
var
i,j,k,l,m,n:longint;
a:array[..,..] of extended;
b:array[..,..] of longint;
procedure swap(var x,y:extended);
var z:extended;
begin
z:=x;x:=y;y:=z;
end; procedure sort(l,r,z:longint);
var
i,j:longint;
x:extended;
begin
i:=l;
j:=r;
x:=a[(l+r) div ,z];
repeat
while a[i,z]<x do inc(i);
while x<a[j,z] do dec(j);
if i<=j then
begin
swap(a[i,z],a[j,z]);
swap(a[i,-z],a[j,-z]);
inc(i);dec(j);
end;
until i>j;
if i<r then sort(i,r,z);
if l<j then sort(l,j,z);
end; begin
readln(n);
for i:= to n do
begin
readln(b[i,],b[i,]);
end; m:=;
for i:= to n do
for j:=i+ to n do
begin
inc(m);
if b[i,]=b[j,] then
begin
a[m,]:=;
a[m,]:=;
end
else
begin
a[m,]:=;
a[m,]:=(b[j,]-b[i,])/(b[j,]-b[i,]);
end;
end; sort(,m,);
l:=m;
while a[l,]= do dec(l);
sort(,l,); if l<= then
begin
if l=m then writeln(l) else writeln(l+);
halt;
end;
j:=;
k:=;
for i:= to l do
begin
if a[i,]<>a[j,] then
begin
inc(k);
j:=i;
end;
end;
if l=m then writeln(k) else writeln(k+);
end.
最新文章
- OAuth认证
- 150925-周五不干活-HTML(CSS),Javascript
- leetcode 278. First Bad Version
- Devexpress treelist 树形控件 实现带三种状态的CheckBox
- 用PyAIML开发简单的对话机器人
- PowerMock.expectNew(Class<;T>; type, Class<;?>;[] parameterTypes, Object... arguments)
- 285.	Inorder Successor in BST
- winform清空DataGridView中的数据 分类: DataGridView 2014-05-19 20:56 180人阅读 评论(0) 收藏
- 转 常用JQuery插件整理
- update-database时出现Cannot attach the file
- CMSIS标准
- Python import hook
- navicat 几个 可用的东西
- Windows下80端口被进程System占用的解决方法
- 订单BOM、销售BOM、标准BOM
- 树莓派 引脚及接口图 AV接口顺序
- 史上最全 Css Hack汇总
- MySQL性能优化(四)-- MySQL explain详解
- hive中 udf,udaf,udtf
- CSS3 grayscale滤镜图片变黑白