FZU2110 Star——————简单题

水深无声 2022-02-21 11:27 141阅读 0赞

# Star #

Accept: 1174 Submit: 3553  
Time Limit: 1000 mSec Memory Limit : 32768 KB

# Problem Description #

Overpower often go to the playground with classmates. They play and chat on the playground. One day, there are a lot of stars in the sky. Suddenly, one of Overpower’s classmates ask him: “How many acute triangles whose inner angles are less than 90 degrees (regarding stars as points) can be found? Assuming all the stars are in the same plane”. Please help him to solve this problem.  
**Input**  
The first line of the input contains an integer T (T≤10), indicating the number of test cases.

For each test case:

The first line contains one integer n (1≤n≤100), the number of stars.

The next n lines each contains two integers x and y (0≤|x|, |y|≤1,000,000) indicate the points, all the points are distinct.

**Output**  
For each test case, output an integer indicating the total number of different acute triangles.  
**Sample Input**  
1  
3  
0 0  
10 0  
5 1000  
**Sample Output**  
1  
**Source**  
“高教社杯”第三届福建省大学生程序设计竞赛

--------------------

给你一些点，让你找出三个点，求找出三个点组成的三角形是锐角三角形的个数(方案数)

简单题，计算下两条边的点积，若点积大于0就说明这里两条边的夹角是锐角

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<cmath>
    #include<cstring>
    #include<string>
    using namespace std;
    typedef long long ll;
    
    struct P{
        
    	ll x,y;
    	
    }p[105];
    
    ll dot(P A, P B, P C)//求AB与AC的点积
    {
        
    	P AB, AC;
    	AB.x = B.x-A.x;
    	AB.y = B.y-A.y;
    	AC.x = C.x-A.x;
    	AC.y = C.y-A.y;
    //	prllf("(%d,%d)*(%d,%d) ",AB.x,AB.y,AC.x,AC.y);
    	return AB.x*AC.x+AB.y*AC.y;
    }
    
    int main()
    {
        
    	ll t,n,x,y;
    	cin>>t;
    	while(t--)
    	{
        
    		cin>>n;
    		for(ll i=0;i<n;++i)
    			cin>>p[i].x>>p[i].y;
    		ll ans = 0;
    		for(ll i=0;i<n;++i)//A
    			for(ll j=i+1;j<n;++j)//B
    				for(ll k=j+1;k<n;++k)//C	AB*AC>0 && BA*BC>0 && CA*CB>0
    				{
        
    					if(dot(p[i],p[j],p[k])>0 && dot(p[j],p[i],p[k])>0 &&dot(p[k],p[i],p[j])>0)
    						ans ++;
    				}
    		cout<<ans<<endl;
    	}
    	return 0;
    }