HDOJ 5621-KK's Point【几何】

妖狐艹你老母 2022-07-11 07:39 96阅读 0赞

# KK's Point #

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)**

Total Submission(s): 1343 Accepted Submission(s): 445

Problem Description

Our lovely KK has a difficult mathematical problem:He points  N(2≤N≤10![Image 1][]5![Image 1][])![Image 1][] points on a circle,there are all different.Now he's going to connect the  N![Image 1][] points with each other(There are no three lines in the circle to hand over a point.).KK wants to know how many points are there in the picture(Including the dots of boundary).

Input

The first line of the input file contains an integer  T(1≤T≤10)![Image 1][], which indicates the number of test cases.  
  
For each test case, there are one lines,includes a integer  N(2≤N≤10![Image 1][]5![Image 1][])![Image 1][],indicating the number of dots of the polygon.

Output

For each test case, there are one lines,includes a integer,indicating the number of the dots.

Sample Input

2
    3
    4

Sample Output

3
    5

Source

[BestCoder Round \#71 (div.2) ][BestCoder Round _71 _div.2_]

题目大意：

在一个圆上有N个点，试这N个点两两相连，并且保证除了圆上的点之外圆中相交的点只能是两线相交。

解题思路：

一个交点是由两条线组成的，所以在保证不能三线相交的前提下，只能选择四边形中的对角线向相交，所以问题转化成N个点能组成多少四边形。

AC代码：

#include<cstdio>
    #include<iostream>
    #define LL unsigned long long
    using namespace std;
    
    int main(){
    	int T;
    	scanf("%d",&T);
    	while(T--){
    		LL n;
    		scanf("%lld",&n);
    		if(n==2)
    		{
    			printf("2\n");
    		}
    		else if(n==3)
    		{
    			printf("3\n");
    		}
    		else
    		{
    			LL ans=n*(n-1)/2*(n-2)/3*(n-3)/4;
    			cout << ans+n << endl; 
    		}
    	}
    	return 0;
    }

[Image 1]: 
[BestCoder Round _71 _div.2_]: http://acm.hdu.edu.cn/search.php?field=problem&key=BestCoder+Round+%2371+%28div.2%29&source=1&searchmode=source