题解 | 数三角

该题目可以通过向量的点积来判断向量的夹角，从而判定三角形中任意两条边的夹角。

A(x1,y1)*B(x2,y2)=x1*x2+y1*y2，这里a，b是向量而非坐标。

可以通过判定a是否小于0来判断夹角是否为钝角。

#include <iostream>
#include <vector>

using namespace std;

pair<int,int> XP(pair<int,int> a,pair<int,int> b){
	b.first-=a.first;
	b.second-=a.second;
	return b;
}//求向量

int XP_J(pair<int,int> a, pair<int,int> b){
	return a.first*b.first+a.second*b.second;
}//求向量积

bool valid(pair<int,int> a,pair<int,int> b,pair<int,int> c){
	if((a.first==b.first&&b.first==c.first)||(a.second==b.second&&b.second==c.second)) return false;
	else if(a.first==b.first||a.first==c.first||b.first==c.first) return true;
	else if((a.first-c.first)*(a.second-b.second)==(a.first-b.first)*(a.second-c.second)) return false;
	else return true;
}//判断三个点是否共线
void Solve(vector<pair<int, int> > P,int n){
	int num=0,ab,ac,bc;
	pair<int,int> a,b,c;//向量
	for(int i=0;i<n-2;++i){
		for(int j=i+1;j<n-1;++j){
			a=XP(P[i],P[j]);
			for(int k=j+1;k<n;++k){
				if(!valid(P[i],P[j],P[k])) continue;
 				b=XP(P[i],P[k]);
				c=XP(P[j],P[k]);
				ab=XP_J(a,b);
				ac=XP_J(a,c);
				bc=XP_J(b,c);
				if(ab<0||ac>0||bc<0)	++num;
			}
		}
	}
	cout<<num<<endl;
}

int main(){
	int n;
	cin>>n;
	vector<pair<int, int> > Point(n);
	for(int i=0;i<n;++i)
		cin>>Point[i].first>>Point[i].second;
	Solve(Point,n);
	return 0;
}