#2175. Geometrija

    ID: 2175 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>TEAM赛事:contest1552来源:qoj.ac数据:公开样例离散化

Geometrija

Geometrija

题目描述

Croatian Open Competition in Informatics Task Geometrija Round 6, March 13th 2021 1 second / 512 MiB / 110 points Task Geometrija You are given n points on the plane, such that no three points lie on the same line. We say that line segments AB and CD cross if they share a point X different from the points A, B, C and D. Let S be the set of all line segments between pairs of the given points. Find the number of segments in S that don’t cross with any other segment in S. Input The first line contains an integer n (3 ≤n ≤1000), the number of points. The following n lines contain integers xi and yi (−109 ≤xi, yi ≤109), the coordinates of the points. Output Output the requested number of segments. Scoring Subtask Points Constraints 3 ≤n ≤40 1 20 3 ≤n ≤200 2 30 3 60 No additional constraints. Examples input input 4 4 1 1 -1 -1 -1 1 1 -1 -1 -1 0 1 1 -1 0 0 output output 4 6 Clarification of the examples: 5 of 6

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

4
1 1
-1 1
-1 -1
1 -1
4

样例 2

4
-1 -1
1 -1
0 1
0 0
6