题目
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 1Sample 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; }