Responsive image

问题 2388 --面积不整三角形

2388: 面积不整三角形

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 2
[提交][状态][讨论版][命题人:]

题目描述

给定平面上n个点(横纵坐标均为整数,可能重合),编号为A1~An让你从中选择Ai,Aj,Ak(i<j<k)组成三角形。有多少种选法使得三角形面积不是整数。

输入描述

第一行一个正整数 n (n<105)
接下来n行,每行两个整数x,y,表示Ai的横纵坐标。(|x|,|y|<1018)

输出描述

输出为一行非负整数,为答案

样例输入

3
0 0
1 1
2 2

样例输出

0

提示

三角形面积公式s=[x1(y2-y3)+x2(y3-y1)+x3(y1-y2)]/2

推导过程:

当三个点A、B、C的坐标分别为A(x1,y1)、B(x2,y2)、C(x3、y3)时,三角形面积为,

S=(x1y2-x1y3+x2y3-x2y1+x3y1-x2y2)。

解:设三个点A、B、C的坐标分别为A(x1,y1)、B(x2,y2)、C(x3、y3)。

那么A、B、C三点可围成一个三角形。AC与AB边的夹角为∠A。

那么向量AB=(x2-x1,y2-y1)、向量AC=(x3-x1,y3-y1)。

令向量AB=a,向量AC=b,

则根据向量运算法则可得,

|a·b|=|a|·|b|·|cosA|,

那么cosA=|a·b|/(|a|·|b|),则sinA=√((|a|·|b|)^2-(|a·b|)^2)/(|a|·|b|)。

那么三角形的面积2*S=|a|·|b|·sinA/2=√((|a|·|b|)^2-(|a·b|)^2)

又a·b=(x2-x1)*(x3-x1)+(y2-y1)*(y3-y1),

那么可得三角形的面积S=(x1y2-x1y3+x2y3-x2y1+x3y1-x2y2)/2=[x1(y2-y3)+x2(y3-y1)+x3(y1-y2)]/2


来源

[提交][状态]
ACM算法攻关部