Codeforces 437E The Child and Polygon
2024-08-21 04:30:59
http://codeforces.com/problemset/problem/437/E
题意:求一个多边形划分成三角形的方案数
思路:区间dp,每次转移只从一个方向转移(L,R连线的某一侧),能保证正确。
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#define ll long long
const ll Mod=;
ll f[][];
struct Point{
double x,y;
Point(){}
Point(double x0,double y0):x(x0),y(y0){}
}p[];
Point operator -(Point p1,Point p2){
return Point(p1.x-p2.x,p1.y-p2.y);
}
double operator *(Point p1,Point p2){
return p1.x*p2.y-p1.y*p2.x;
}
int read(){
int t=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
ll solve(int l,int r){
if (f[l][r]!=-) return f[l][r];
if (l>r) return f[l][r]=;
if (l+==r) return f[l][r]=;
f[l][r]=;
for (int i=l+;i<r;i++){
if ((p[r]-p[l])*(p[i]-p[l])<)
(f[l][r]+=(solve(l,i)*solve(i,r))%Mod)%=Mod;
}
return f[l][r];
}
int main(){
int n=read();
for (int i=;i<=n;i++) p[i].x=read(),p[i].y=read();
for (int i=;i<=n;i++)
for (int j=;j<=n;j++)
f[i][j]=-;
double res=;
p[n+]=p[];
for (int i=;i<=n;i++)
res+=p[i]*p[i+];
if (res<){
for (int i=;i<=n/;i++) std::swap(p[i],p[n-i+]);
}
printf("%lld\n",solve(,n));
}
最新文章
- Nginx反向代理多虚拟主机代理
- iOS开发——高级篇——内存分析,Instruments
- ASP.Net MVC开发基础学习笔记(1):走向MVC模式
- C++学习基础九——继承
- 生成Apk遇到的问题
- MySQL错误: could not retrieve transation read-only status server
- python Django 学习笔记(六)—— 写一个简单blog做增删改练手
- mvc4 http错误403.14 forbidden
- iOS内存管理retain,assign,copy,strong,weak
- hadoop的wordcount的改动版
- 使用SQL Server Management Studio 创建作业备份数据库
- Vue项目的部署
- iOS10 相册权限
- js或jquery实现点击某个按钮或元素显示div,点击页面其他任何地方隐藏div
- Chapter 5 Blood Type——7
- Spring Boot admin 2.0 详解
- maven wrapper使用本地maven
- makefile笔记2 - makefile总述
- PXE高效能批量网络装机
- 【模板】splay维护序列
热门文章
- 【HDOJ】1315 Basic
- tarjan缩点
- 【转】Android UI系列-----时间、日期、Toasts和进度条Dialog
- WEB/ WCF安全认证
- 模型-视图-控制器 (MVC)
- 限定checkbox最多选中数量
- 线段树求逆序数方法 HDU1394&;amp;&;amp;POJ2299
- winrar3.7-winrar4.0的注冊码
- ExtJS4.2学习(11)——高级组件之Grid
- Java基础知识强化47:StringBuffer类之StringBuffer的三个面试题