返回顶部

收藏

判断N个点能否构成N凸多边形

更多
#include<iostream.h>
const int N=4;
int tt(double p[][2],int a,int b) //a为下标,不能为float
{
       int temp[N],k=0;
       double t;
       for(int i=0;i<N;i++)
       {
              if(i==a||i==b)
              { 
                     continue;
              }
          t=p[i][0]*(p[b][1]-p[a][1])+(p[a][0]-p[b][0])*p[i][1]-p[a][0]*p[b][1]+p[b][0]*p[a][1];
              if(t==0)
                     return 0;
              else
                     if(t>0)
                            temp[k++]=1;
                     else
                            temp[k++]=-1;
       }
       for(int j=1;j<k;j++)
       {
              if(temp[0]!=temp[j]) return 0;
       }
       return 1;
}
int    real(double p[][2])
{
       int flag[N],m=0;
       for(int i=0;i<N;i++)
       {
              flag[i]=0;
       }
       for( i=0;i<N;i++)
       {
              for(int j=1;j<N;j++)
              {
                     if(flag[j]) continue;
                     if(tt(p,m,j))
                     {
                           flag[m]=1;
                           m=j;
                            break;
                     }
              }
       }
       flag[m]=1;
       for(i=0;i<N;i++)
       {
              if(flag[i]==0)
                     return 0;
       }
       if(tt(p,0,m)) return 1;
    return 0;
}
void main()
{
       double p[N][2];
       char ch='y';
       while (ch=='y'||ch=='Y')
       {
              cout<<"请输入这N个点坐标:"<<endl;
           for(int i=0;i<N;i++)
              {
                     cout<<" 第"<<i<<"个点坐标:";
                  cin>>p[i][0]>>p[i][1];
                  //cin>>**p>>*(*p+1);
                  cout<<p[i][0]<<","<<p[i][1]<<endl;
              }
           if (real(p))
                  cout<<"能";
           else
                  cout<<"不能";
           cout<<endl<<"是否继续判断?(继续请输入y&Y)";
              cin>>ch;
       }
}
//该片段来自于http://outofmemory.cn

标签:c++,算法

收藏

0人收藏

支持

0

反对

0

»更多 您可能感兴趣的代码
  1. 2014-10-01 12:24:21打印杨辉三角 by 跳跳虎
  2. 2014-10-26 11:43:57递归法求二进制数一 by 童学芬
  3. 2014-10-29 17:12:53C++算法之克鲁斯卡尔算法 by niutao.linux
  4. 2014-11-02 10:06:44C++算法之数据选择问题 by niutao.linux
  5. 2014-11-19 12:29:49Fibonacci 搜索法 by niutao.linux
  6. 2014-11-22 10:11:32求一列数的最小公倍数 by qqmmcc
  7. 2012-11-13 20:16:04c++使用堆,查找数组中最小的k个数 by 香格里拉登
  8. 2014-03-28 20:20:14C++算法之线性结构处理 by lucasli
  9. 2014-05-18 21:55:46大数阶乘算法 by lucasli
  10. 2014-05-19 16:50:59k阶裴波那契序列 by 童学芬
  11. 2014-05-22 14:43:08自编随机数 by sxgkwei
相关聚客文章
  1. dianlujitao 发表 2014-10-17 13:14:36 CodeForces 23B Party
  2. dianlujitao 发表 2014-10-17 13:32:08 POJ 2339 Rock, Scissors, Paper
  3. bystander 发表 2013-04-11 10:50:25 模板栈以及中缀表达式求值(C++实现)
  4. dianlujitao 发表 2014-10-17 13:42:33 POJ 3844 Divisible Subsequences
  5. dianlujitao 发表 2014-10-17 13:45:25 POJ 3122 Pie
  6. bystander 发表 2013-04-16 00:42:58 模板优先级队列及堆排序(C++实现)
  7. dianlujitao 发表 2014-10-17 13:52:22 POJ 2388 Who’s in the Middle
  8. surgesoft 发表 2014-10-28 08:01:58 LeetCode OJ: Restore IP Addresses
  9. espace 发表 2015-07-18 17:43:14 Two Sum
  10. abyssss 发表 2014-05-20 03:23:39 数据结构 最小堆 数组实现
  11. dianlujitao 发表 2014-10-17 13:56:48 POJ 1611 The Suspects
  12. bystander 发表 2013-05-15 10:37:24 倒水问题求解(C++)

发表评论