凸多边形的判定方法

我的思路：

首先当然要在平面直角坐标系中知道每个点的坐标

1. 将n边形的顶点按照横坐标从小到大排序，记为a[0]~a[n-1]。

2. 分别求出a[0]与a[1]~a[n-1]连线的斜率，记作k[1]~k[n-1]。

3. 将这些点按照其斜率（ k[1] ~ k[n-1] ) 从小到大排序,重新记作a[1]~a[n-1]。

4. 按照新的顶点序号顺序分别求出相邻两个点连线的斜率，（即k1[i]等于a[i]与a[i+1]连线的斜率）记作k1[0]~k1[n-1],。

5. 分析这个k1序列，如果它是分两段递增的，比如-50，-20，-5，5，30，-40，-15，0，15，20这样能分割成两个递增序列的话，就说明该多边形是凸的。

6. 对于斜率不存在的特殊情况，只需要让它的值为MAX或-MAX即可（MAX很大）。

关于这样判断的原理和可靠性，自己脑部补一个正六边形模拟一下上面的操作大概就懂了。

给个例题：ZOJ3537

题意：给出n边形的n个顶点的坐标（如果多边形是凹多边形就输出不能切），切凸多边形时每次只能在顶点和顶点间切，每切一次都有相应的代价。现在已经给出计算代价的公式，所有分割线不能相交，问把多边形切成n-2个三角形的最小代价是多少。

AC代码：

#include<iostream>
#include<queue>
#include<algorithm>
#include<math.h>
#include<cstdio>
#include<cstring>
#define MAX 100000000
using namespace std;
struct node {
 int x;
 int y;
 float z;
}a[400];
bool cmpz(const node &a,const node &b) {
 return a.z < b.z;
}
bool cmpx(const node &a,const node &b) {
 return a.x < b.x;
}
int mi(int a,int b) {
 if(a<b) return a;
 return b;
}
int main() {
 //freopen("1.txt","r",stdin);
 int n,p,qw,i,j,k,tu,cost[400][400],dp[400][400];
 float k1[400];
 while(scanf("%d%d",&n,&p)!=EOF) {
  tu=1;
  for(i=0;i<n;i++) scanf("%d%d",&a[i].x,&a[i].y);
  sort(a,a+n,cmpx);
  a[0].z=-MAX;
  if(a[0].x==a[1].x) { //求斜率
   if(a[0].y<a[1].y) a[1].z=20001;
   else a[1].z=-20001;
  }
  else a[1].z=((float)(a[0].y-a[1].y))/((float)(a[0].x-a[1].x));
  for(i=2;i<n;i++) a[i].z=((float)(a[0].y-a[i].y))/((float)(a[0].x-a[i].x));
  sort(a,a+n,cmpz);
  /*
  for(i=0;i<n;i++) {
   printf("%d,%d,%f\n",a[i].x,a[i].y,a[i].z);
  }
  */
  k1[0]=a[1].z;
  k1[n-1]=a[n-1].z;
  for(i=1;i<n-1;i++) {
   if(a[i].x==a[i+1].x) k1[i]=20001;
   else k1[i]=((float)(a[i+1].y-a[i].y))/((float)(a[i+1].x-a[i].x));
  }
  /*
  for(i=0;i<n;i++) {
   printf("%f\n",k1[i]);
  }
  */
  qw=0;
  for(i=0;i<n-1;i++) {
   if(qw==0) {
    if(k1[i]<k1[i+1]) ;
    else qw=1;
    continue;
   }
   if(qw==1) {
    if(k1[i]<k1[i+1]) ;
    else tu=0;
   }
  }
  if(tu==0) printf("I can't cut.\n");
  else {
   for(i=0;i<n;i++)
    for(j=i+2;j<n;j++)
     cost[i][j]=cost[j][i]=abs(a[i].x+a[j].x)*abs(a[i].y+a[j].y)%p;
   for(i=0;i<n;i++) {
             for(j=i;j<n;j++)
     dp[i][j]=MAX;
             dp[i][(i+1)%n]=0;
         }
   for(i=n-3;i>=0;i--) {
             for(j=i+2;j<n;j++) {
                 for(k=i+1;k<j;k++) {
                     dp[i][j]=mi(dp[i][j],dp[i][k]+dp[k][j]+cost[i][k]+cost[k][j]);
                 }
             }
         }
         if(n==3) printf("0\n");
         else printf("%d\n",dp[0][n-1]);
  }
 }
}