hdu3685(几何重心与凸包结合)
结合 几何 凸包
2023-09-11 14:14:43 时间
题意:给一个多边形(有可能是凹多边形)。问有多少种可以使得它稳定放置的方式。当然稳定的原则就是重心做垂线在支撑点之内。
解法:由于有可能是凹多边形,所以先求出多边形的凸包,这是在放置时候会接触地面的全部点。
然后将重心与每天凸边推断是否稳定。
代码:
/****************************************************** * @author:xiefubao *******************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> #include <vector> #include <algorithm> #include <cmath> #include <map> #include <set> #include <string.h> //freopen ("in.txt" , "r" , stdin); using namespace std; #define eps 1e-8 #define zero(_) (_<=eps) const double pi=acos(-1.0); typedef long long LL; const int Max=100010; const LL INF=0x3FFFFFFF; struct point { double x,y; }; point points[50005]; point focus; int top; int stack[50005]; int N; double mult(point a,point b,point c) { a.x-=c.x; a.y-=c.y; b.x-=c.x; b.y-=c.y; return a.x*b.y-a.y*b.x; } double dis(const point& a,const point& b) { return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); } bool operator<(point a,point b) { if(mult(a,b,points[0])>0||(mult(a,b,points[0])==0 && a.x<b.x)) return true; else return false; } point OK(point a,point b,point c) { point ans; ans.x=(a.x+b.x+c.x)/3; ans.y=(a.y+b.y+c.y)/3; return ans; } void getFocus(point& focus,point* points,int N) { focus.x=0; focus.y=0; double base=0; for(int i=2; i<N; i++) { double t=mult(points[0],points[i-1],points[i]); point pp=OK(points[0],points[i-1],points[i]); focus.x+=t*pp.x; focus.y+=t*pp.y; base+=t; } focus.x/=base; focus.y/=base; } int getans() { int ans=0; for(int i=0; i<top; i++) { double l=dis(focus,points[stack[i]]); double r=dis(focus,points[stack[i+1]]); double u=dis(points[stack[i]],points[stack[i+1]]); if(l+u>r&&r+u>l) ans++; } double l=dis(focus,points[stack[top]]); double r=dis(focus,points[stack[0]]); double u=dis(points[stack[top]],points[stack[0]]); if(l+u>r&&r+u>l) ans++; return ans; } void graham(int n) { int mi=0; for(int i=1; i<n; i++) { if(points[i].y<points[mi].y||(points[i].y==points[mi].y&&points[i].x<points[mi].x)) mi=i; } point a=points[0]; points[0]=points[mi]; points[mi]=a; sort(points+1,points+n); stack[0]=0; stack[1]=1; stack[2]=2; top=2; for(int i=3; i<n; i++) { while(top>0&&mult(points[stack[top]],points[stack[top-1]],points[i])>=0) { top--; } stack[++top]=i; } } int main() { int t; cin>>t; while(t--) { scanf("%d",&N); for(int i=0; i<N; i++) { scanf("%lf%lf",&points[i].x,&points[i].y); } getFocus(); graham(N); cout<<getans()<<endl; } return 0; }
相关文章
- shell脚本--编写CGI代码(shell结合html)以及环境变量
- [转]结合轮廓显示,实现完整的框选目标(附Demo代码)
- EPPlus与Excel完美的结合
- 《Android进阶之光》--RxJava结合Retrofit访问网络
- php 结合md5的加密,解密方法
- 【YOLOv8/YOLOv7/YOLOv5/YOLOv4/Faster-rcnn系列算法改进NO.62】结合NeurIPS 2022年GhostnetV2网络模块
- 【PyQT5编程】Pycharm结合QtDesigner使用示例:创建登录窗体
- 【STM32H7】第30章 ThreadX GUIX炫酷实用的时钟表盘设计,结合硬件RTC实时时钟
- ML之FE:风控场景之金融评分卡模型之利用LoR模型权重变量系数正负符号结合p-value/P值大小实现变量筛选
- 结合邻域连接法的蚁群优化(NACO)求解TSP问题(Matlab代码实现)
- SVM与基于马氏距离的径向基函数(MDRBF)核结合组合(Matlab代码实现)
- 华为双机热备与NAT的结合
- Spring Quartz结合Spring mail定期发送邮件
- rootkit——一种特殊的恶意软件,它的功能是在安装目标上隐藏自身及指定的文件、进程和网络链接等信息,一般都和木马、后门等其他恶意程序结合使用
- 利用神经网络进行网络流量识别——特征提取的方法是(1)直接原始报文提取前24字节,24个报文组成596像素图像CNN识别;或者直接去掉header后payload的前1024字节(2)传输报文的大小分布特征;也有加入时序结合LSTM后的CNN综合模型
- 目标检测算法——YOLOv5/YOLOv7改进之结合MobileOne结构(高性能骨干|仅需1ms)