Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

fzoj 4952 哨兵

题目链接

当然了前提是你得有fzoj的账号
(老fzoj 不是新的
传送门

题目描述

在一个军事基地附近,有一个战壕阵地。在夜间,大部分士兵需要休息,留三个士兵来负责守卫和警戒,如果两个士兵在同一条战壕中并且中间没有第三个人的话,他们是能够看到彼此的。
出于安全考虑,在布置三名士兵时,需要保证他们每个士兵都能看到另外两个,问:他们有多少种站位方法?

输入

第一行,包含一个正整数N(1 ≤ N ≤ 20),表示有N条战壕;
接下来N行,每行四个正整数X1, Y1, X2, Y2(均<=1000),(X1,Y1)表示战壕一端的坐标,(X2,Y2)表示另一端的坐标。
多条战壕可能会交叉、重叠、共享同一个端点。

输出

输出三个士兵可以站位的方法数。

样例输入,输出

想说的话

再给我一万次机会我也不会相信这是一套noip模拟题

题解

这个题看起来很简单
就是在给你的图中
找三角形
怎么找呢
显然不可直接找
可以用计算几何的思想
当三条直线没有两条互相平行,并且存在两对直线它们的交点不同时
可以构成三角形
相交的交点以及平行之类的全部都是计算几何的内容
由于函数名字过多
而且这是我第一次写计算几何
所以函数名称都用的拼音2333
下面贴代码

代码

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注

隐藏