Codeforces Round #308 (Div. 2) D. Vanya and Triangles 水题

时间：2023-03-08 20:40:53
Codeforces Round #308 (Div. 2) D. Vanya and Triangles 水题

D. Vanya and Triangles

Time Limit: 20 Sec

Memory Limit: 256 MB

题目连接

http://codeforces.com/contest/552/problem/D

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

4
0 0
1 1
2 0
2 2

Sample Output

3

HINT

题意

平面上给你n个点，然后问你能构成多少个三角形

题解：

n^3暴力跑一法就过了……

是数据太水，还是我太屌？

代码：

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

#include <stack>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define test freopen("test.txt","r",stdin)

#define maxn 2000001

#define mod 10007

#define eps 1e-5

const int inf=0x3f3f3f3f;

const ll infll = 0x3f3f3f3f3f3f3f3fLL;

inline ll read()

{

    ll x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

//**************************************************************************************

#include<cstdio>

#include<cmath>

using namespace std;

struct point

{

    int x,y;

    friend int operator *(point A,point B){return A.x*B.y-A.y*B.x;}

    friend point operator -(point A,point B){point C;C.x=A.x-B.x;C.y=A.y-B.y;return C;}

}p[];

int ans,n;

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++)

        scanf("%d%d",&p[i].x,&p[i].y);

    for(int i=;i<=n-;i++)

        for(int j=i+;j<n;j++)

            for(int k=j+;k<=n;k++)

                if((p[i]-p[j])*(p[j]-p[k]))ans++;

                    printf("%d",ans);

    return ;

}

相关文章