AOJ 796.数三角形

166

题目


Time Limit: 5000 ms
Case Time Limit: 5000 ms
Memory Limit: 128 MB
Total Submission: 112
Submission Accepted: 40

Description
ACMer最讨厌大段大段的题目描述了,尤其当题目描述是英文的时候。还好,1243France为大家准备了一道简洁且简单的问题。
给出平面上n个点的坐标,求这n个点总共可以围成多少个面积大于0的三角形。
保证每个点的横纵坐标均为整数且绝对值小于等于100。
保证给出点当中没有重点



Input
输入数据包含多组,EOF结束
每组数据第一行包含一个数n,表示有n个点(1 ≤ n ≤ 200)
之后n行每行两个整数x,y表示一个点和横坐标及纵坐标(- 100 ≤ x,y≤ 100)



Output
对于每组输入,输出一个数k
表示总共能围成k个面积大于0的三角形



Sample Input
4
0 0
1 1
2 0
2 2
1
1 1



Sample Output
3
0


题解


只需要保证不存在三个点在一条直线即可

(包括横坐标相同、纵坐标相同、斜率相同)

(貌似我写的没有考虑到斜率不存在的情况欸~不过AC了)


代码



#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <stack>
using namespace std;
 
#define REP(n) for(int o=0;o<n;o++)
 
pair<int,int> p[205];
bool Do() {
    int n;
    if(scanf("%d",&n) == EOF)
        return false;
    REP(n) {
        int x,y;
        scanf("%d%d",&x,&y);
        p[o] = pair<int,int>(x,y);
    }
    int cnt = 0;
    for(int i = 0;i < n;i++)
        for(int j = i + 1;j < n;j++)
            for(int k = j + 1;k < n;k++) {
                if(i < j&&j < k) {
                    pair<int,int >a = p[i],b = p[j],c = p[k];
                    if(!(
                        (a.first == b.first&&a.first == c.first) ||
                        (a.second == b.second&&a.second == c.second) ||
                        ((double)(a.first - b.first) / (double)(a.second - b.second) ==
                            (double)(c.first - b.first) / (double)(c.second - b.second))
                        )) {
                        cnt++;
                        //printf("%d %d %d\n",i,j,k);
                    }
                }
            }
    printf("%d\n",cnt);
 
    return true;
}
 
int main() {
    while(Do());
    return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论