11123专题

uva 11123 - Counting Trapizoid(容斥+几何)

题目链接:uva 11123 - Counting Trapizoid 题目大意:给定若干个点,问有多少种梯形,不包括矩形,梯形的面积必须为正数。因为是点的集合,所以不会优重复的点。 解题思路:枚举两两点,求出该条直线,包括斜率k,偏移值c,以及长度l。已知梯形的性质,一对对边平行,也就是说一对平行但是不相等的边。 所以将所有线段按照斜率排序,假设对于某一斜率,有m条边,那么这m条边