【25.33%】【codeforces 552D】Vanya and Triangles
time limit per test4 seconds
memory limit per test512 megabytes
inputstandard input
outputstandard output
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.
Examples
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
Note
Note to the first sample test. There are 3 triangles formed: (0, 0) - (1, 1) - (2, 0); (0, 0) - (2, 2) - (2, 0); (1, 1) - (2, 2) - (2, 0).
Note to the second sample test. There is 1 triangle formed: (0, 0) - (1, 1) - (2, 0).
Note to the third sample test. A single point doesn’t form a single triangle.
【题目链接】:http://codeforces.com/contest/552/problem/D
【题解】
时限给的宽。
直接暴力枚举就可以了。
判断3条线是否相交
O(N^3);
1500MS过。。
MAXN=2000;
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%I64d",&x)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int MAXN = 2e3+100;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
struct abc
{
int x,y;
};
int n;
abc a[MAXN];
bool xj(int t1,int t2,int t3)
{
int x1 = a[t1].x,y1 = a[t1].y;
int x2 = a[t2].x,y2 = a[t2].y;
int x3 = a[t3].x,y3 = a[t3].y;
if ((x2-x1)*(y3-y2)-(y2-y1)*(x3-x2)==0) return true;
else
return false;
}
int main()
{
//freopen("F:\\rush.txt","r",stdin);
rei(n);
rep1(i,1,n)
rei(a[i].x),rei(a[i].y);
LL ans = 0;
rep1(i,1,n-2)
rep1(j,i+1,n-1)
rep1(k,j+1,n)
if (!xj(i,j,k))
ans++;
printf("%I64d\n",ans);
return 0;
}
最新文章
- Jeet – 先进,直观,灵活的 CSS 网格系统
- 关于CSS的那些事?
- mysql中char,varchar,text区别总结
- Xwindow 连接 RHEL 5
- js中隐式类型转换测试
- A题进行时--浙大PAT 1021-1030
- Python 获取Facebook用户的Friends的爱好中的Top10
- 一个SQL update语句
- QT 遍历目录查找指定文件(比较简单)
- java中使用fastjson、jackson、json-lib解析JSON-------------------妈妈再也不用担心JSON解析
- JavaSE教程-01初识Java-思维导图
- 用C#实现微信“跳一跳”小游戏的自动跳跃助手
- ORM对象关系映射之使用GreenDAO进行CRUD操作
- HYPER -V 独立安装的 2016版本 中文版 下载好慢啊
- Centos7常用操作
- asp.net针对SQLSERVER数据库备份和恢复的一揽子问题解决
- 05 Zabbix triggers--action--event
- 微软Power BI 每月功能更新系列——12月Power BI 新功能学习
- MYSQL自动备份策略的选择与实践
- struts2的异常配置
热门文章
- 洛谷——P1823 音乐会的等待
- amazeui学习笔记二(进阶开发4)--JavaScript规范Rules
- Log4j.properties 属性详解以及 LOG4J日志级别详解
- 102.tcp实现多线程连接与群聊
- 1.2 Use Cases中 Log Aggregation官网剖析(博主推荐)
- 2. Vue基础语法
- COGS——C66. [HAOI2004模拟] 数列问题
- 一个DDOS病毒的分析(一)
- AspJpeg2.0组件教程完整版 aspjpeg教程...
- 洛谷—— P1091 合唱队形