本文主要是介绍FZOJ2110 star(DFS),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
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
Sample Input
1 3 0 0 10 0 5 1000
Sample Output
1
#include<stdio.h> #include<math.h> typedef struct nn {double x1,y1; }node; void cmp(double *a,double *b,double *c) {double tem;if(*a<*b){tem=*a;*a=*b;*b=tem;}if(*a<*c){tem=*a;*a=*c;*c=tem;} } double cacreat(double x1,double y1,double x2,double y2) {double edglen;edglen=sqrt(pow(x1-x2,2.0)+pow(y1-y2,2.0));return edglen; } int pandu(double a,double b,double c) {if(b*b+c*c-a*a>0)return 1;return 0; } double x[105],y[105]; node s[3]; int vist[105],n,sum; void dfs(int cout,int j) {double edg1,edg2,edg3;int i;s[cout].x1=x[j];s[cout].y1=y[j];if(cout==2){edg1=cacreat(s[0].x1,s[0].y1,s[1].x1,s[1].y1);edg2=cacreat(s[0].x1,s[0].y1,s[2].x1,s[2].y1);edg3=cacreat(s[1].x1,s[1].y1,s[2].x1,s[2].y1);cmp(&edg1,&edg2,&edg3);if(pandu(edg1,edg2,edg3)!=0)sum++;return ;}for(i=j+1;i<n;i++)if(vist[i]==0){vist[i]=1;dfs(cout+1,i);vist[i]=0;} } int main() {int i,t;scanf("%d",&t);while(t--){scanf("%d",&n);for(i=0;i<n;i++){scanf("%lf%lf",&x[i],&y[i]);vist[i]=0;}sum=0;for(i=0;i<n;i++){vist[i]=1;dfs(0,i);vist[i]=0;}printf("%d\n",sum);} }
这篇关于FZOJ2110 star(DFS)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!