首页 > ACM题库 > HDU-杭电 > HDU 3629-Convex[解题报告]HOJ
2014
11-29

HDU 3629-Convex[解题报告]HOJ

Convex

问题描述 :

Your task is very simple. You will get the coordinates of n points in a plane. It is guaranteed that there are no three points on a straight line. You can choose any four points from these points to construct a quadrangle. Now, please tell me how many convex quadrangles you can construct.

输入:

The first line of input contain an integer z (z ≤ 20), indicating the number of test cases.
For each test case, the first line contain an integer n (4 ≤ n ≤ 700), indicating the number of points. Each of the next n lines contains two integers x and y (-1000000 ≤ x, y ≤ 1000000), indicating the coordinate of corresponding point.

输出:

The first line of input contain an integer z (z ≤ 20), indicating the number of test cases.
For each test case, the first line contain an integer n (4 ≤ n ≤ 700), indicating the number of points. Each of the next n lines contains two integers x and y (-1000000 ≤ x, y ≤ 1000000), indicating the coordinate of corresponding point.

样例输入:

2
4
0 0
0 1
1 0
1 1
4
0 0
1 0
0 1
-1 -1

样例输出:

1
0

#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll __int64
int T;
ll n;
double x[700],y[700],p[1400],pi=acos(-1.0);
int main()
{
 scanf("%d",&T);
 while(T--)
 {
 scanf("%I64d",&n);
 for(int i=0;i<n;i++)scanf("%lf%lf",x+i,y+i);
 ll ans=n*(n-1)*(n-2)*(n-3)/24,C=(n-1)*(n-2)*(n-3)/6;
 for(int i=0;i<n;i++)
 {
 int t=0,top=0;
 for(int j=0;j<n;j++)
 if(j^i)p[t++]=atan2(y[j]-y[i],x[j]-x[i]);
 sort(p,p+t);
 for(int j=0;j<n-1;j++)p[t++]=p[j]+pi*2;
 //for(int j=0;j<t;j++)printf("%f ",p[j]/pi*180.0);puts("");
 ll sum=0;
 for(int j=0;j<n-1;j++)
 {
 while(p[top+1]-p[j]<pi-1e-10/*fuck eps*/)++top;
 int cnt=top-j;
 if(cnt>=2)sum+=cnt*(cnt-1)/2;
 //printf("j=%d,cnt=%d\n",j,cnt);
 }
 //printf("%lld %lld\n",C,sum);
 ans-=C-sum;
 }
 printf("%I64d\n",ans);
 }
}

  1. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法

  2. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  3. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环