分类 计算几何 下的文章

BZOJ 1610: [Usaco2008 Feb]Line连线游戏

题目描述Farmer John最近发明了一个游戏,来考验自命不凡的贝茜。游戏开始的时 候,FJ会给贝茜一块画着N (2 <= N <= 200)个不重合的点的木板,其中第i个点 的横、纵坐标分别为X_i和Y_i (-1,000 <= X_i <=1,000; -1,000 <= Y_i <= 1,000)。 贝茜可以选两个点画一条过它们的直线,当且仅当平面上不存在与画出直线 平行的直线。游戏结束时贝茜的得分,就是她画出的直线的总条数。为了在游戏 中胜出,贝茜找到了你,希望你帮她计算一下最大可能得分。输入第1行: 输入1个正整数:N第2..- 阅读剩余部分 -

BZOJ [HNOI2008]水平可见直线

题目描述在xoy直角坐标平面上有n条直线L1,L2,...Ln,若在y值为正无穷大处往下看,能见到Li的某个子线段,则称Li为可见的,否则Li为被覆盖的.例如,对于直线:L1:y=x; L2:y=-x; L3:y=0则L1和L2是可见的,L3是被覆盖的.给出n条直线,表示成y=Ax+B的形式(|A|,|B|<=500000),且n条直线两两不重合.求出所有可见的直线.输入第一行为N(0 < N < 50000),接下来的N行输入Ai,Bi输出从小到大输出可见直线的编号,两两中间用空格隔开,最后一个数字后面也必须有个空格样例输入3-1 01 00 0样例输出- 阅读剩余部分 -