见代码。

 /*
凸包(稳定凸包)
题意:给出一些点,这些点要么是凸包的顶点要么是边上的。
证明每条边上都至少有3个点。
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<math.h>
using namespace std;
typedef long long int64;
//typedef __int64 int64;
typedef pair<int64,int64> PII;
#define MP(a,b) make_pair((a),(b))
const int maxn = ;
const int inf = 0x7fffffff;
const double pi=acos(-1.0);
const double eps = 1e-; struct Point {
double x,y;
bool operator < ( const Point p ) const {
return y<p.y||(y==p.y&&x<p.x);
}
}res[ maxn ],pnt[ maxn ];
bool flag[ maxn ][ maxn ];//f[i][j]:点ij之间是否还有点
bool ok[ maxn ];//ok[i]:i是否是凸包的顶点 double xmult( Point sp,Point ep,Point op ){
return (sp.x-op.x)*(ep.y-op.y)-(sp.y-op.y)*(ep.x-op.x);
} double dis2( Point a,Point b ){
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
} double dis( Point a,Point b ){
return sqrt( dis2(a,b) );
} bool PointOnLine( Point a,Point L,Point R ){
return ( fabs(xmult( a,L,R ))<eps )&&( (a.x-L.x)*(a.x-R.x)<eps )&&( (a.y-L.y)*(a.y-R.y)<eps );
} int Garham( int n ){
int top = ;
sort( pnt,pnt+n );
if( n== ) return ;
else res[ ] = pnt[ ];
if( n== ) return ;
else res[ ] = pnt[ ];
if( n== ) return ;
else res[ ] = pnt[ ];
for( int i=;i<n;i++ ){
while( top>&&xmult( res[top],res[top-],pnt[i] )>= )
top--;
res[ ++top ] = pnt[ i ];
}
int tmp = top;
res[ ++top ] = pnt[ n- ];
for( int i=n-;i>=;i-- ){
while( top!=tmp&&xmult( res[top],res[top-],pnt[i] )>= )
top--;
res[ ++top ] = pnt[ i ];
}
return top;
} int main(){
int T;
scanf("%d",&T);
while( T-- ){
int n;
scanf("%d",&n);
for( int i=;i<n;i++ )
scanf("%lf%lf",&pnt[i].x,&pnt[i].y);
if( n<= ){
puts("NO");
continue;
}//至少要6个点
int cnt = Garham( n );
memset( ok,false,sizeof( ok ) );
memset( flag,false,sizeof( flag ) );
for( int i=;i<n;i++ ){
for( int j=;j<cnt;j++ ){
if( pnt[i].x==res[j].x&&pnt[i].y==res[j].y ){
ok[ i ] = true;
break;
}
}
}
for( int i=;i<n;i++ ){
if( !ok[i] ){
for( int j=;j<cnt;j++ ){
if( PointOnLine( pnt[i],res[j],res[(j+)%cnt]) ){
flag[ j ][ (j+)%cnt ] = true;
}
}
}
}
bool ans = true;
for( int i=;i<cnt;i++ ){
if( flag[ i ][ (i+)%cnt ]==false ){
ans = false;
break;
}
}
if( ans ) printf("YES\n");
else puts("NO");
}
return ;
}

最新文章

  1. AngularJS2
  2. spring mvc4的日期/数字格式化、枚举转换
  3. VS SuppressMessage忽略特定方法的警告信息
  4. 安装oracle pl/sql developer
  5. 初步掌握HBase
  6. 【转】使用unity3d需要注意到细节
  7. [Android学习笔记]LayoutParams的使用
  8. IntelliJ IDEA 开发scala
  9. POJ - 3666 Making the Grade(dp+离散化)
  10. 【js】性能问题
  11. js基本语法汇总
  12. sql 多条记录插入
  13. codeblocks: 使用静态(static)链接库(pcre)的配置
  14. HDU 1027(数字排列 STL)
  15. write命令帮助文档(ubuntu 18.04)
  16. [译]使用NuGet管理共享代码
  17. CPU与内存互联的架构演变
  18. ELK(elasticsearch+kibana+logstash)搜索引擎(一): 环境搭建
  19. POP3_使用SSL链接邮箱并获取邮件
  20. Leveldb 使用说明文档

热门文章

  1. C#中 多线程执行含有返回值的函数
  2. C# 线程--第二线程方法
  3. 【ios控件】UIScrollView 事件说明
  4. (转)如何在高并发分布式系统中生成全局唯一Id
  5. docker &amp; nodejs &amp; mongodb
  6. info sed 中文不完全文档
  7. 你早该这么玩Excel 读书笔记
  8. lex&amp;yacc 9
  9. poj 1659 Frogs&#39; Neighborhood Havel-Hakimi定理 可简单图定理
  10. php5 图片验证码一例