Vanya and Triangles 暴力枚举

枚举法:

枚举法是利用计算机速度快, 精度高的特点, 对要解决的问题所有可能情况进行霸道的, 一个不漏检验, 从中找出符合要求的答案。

特点:

1. 得到的结果一定正确。

2. 可能做了很多无用功,效率低下。

3. 一般会涉及到极值。

4. 数据量大的话可能造成时间崩溃。

结构:

循环结构。

基本思路:

1. 确定枚举对象, 枚举范围, 判定条件。

2. 枚举可能的解, 验证是否是问题的解。

Vanya and Triangles :

M - Vanya and Triangles

Crawling in process... Crawling failed Time Limit:4000MS     Memory Limit:524288KB     64bit IO Format:%I64d & %I64u

SubmitStatus

Description

Vanya got bored and he painted n distinct points on the plane. After that he connected all the points pairwise and saw that as a result many triangles were formed with vertices in the painted points. He asks you to count the number of the formed triangles with the non-zero area.

Input

The first line contains integer n (1 ≤ n ≤ 2000) — the number of the points painted on the plane.

Next n lines contain two integers each xi, yi ( - 100 ≤ xi, yi ≤ 100) — the coordinates of the i-th point. It is guaranteed that no two given points coincide.

Output

In the first line print an integer — the number of triangles with the non-zero area among the painted points.

Sample Input

Input

4
0 0
1 1
2 0
2 2

Output

3

Input

3
0 0
1 1
2 0

Output

1

Input

1
1 1

Output

0

 
 
#include<stdio.h>

struct point{
int x, y;
}p[3100]; int main()
{
int n, ans = 0;
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d%d", &p[i].x, &p[i].y);
for(int i = 1; i < n - 1; i++)
for(int j = i + 1; j < n; j++)
for(int k = j + 1; k <=n; k++)
if((p[i].y - p[j].y)*(p[k].x - p[i].x) != (p[k].y - p[i].y)*(p[i].x - p[j].x))
ans++;
printf("%d\n", ans);
return 0;
}

  

  

 
上一篇:IOS设计模式的六大设计原则之单一职责原则(SRP,Single Responsibility Principle)


下一篇:【设计原则和编程技巧】单一职责原则 (Single Responsibility Principle, SRP)