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));
}

最新文章

  1. Nginx反向代理多虚拟主机代理
  2. iOS开发——高级篇——内存分析,Instruments
  3. ASP.Net MVC开发基础学习笔记(1):走向MVC模式
  4. C++学习基础九——继承
  5. 生成Apk遇到的问题
  6. MySQL错误: could not retrieve transation read-only status server
  7. python Django 学习笔记(六)—— 写一个简单blog做增删改练手
  8. mvc4 http错误403.14 forbidden
  9. iOS内存管理retain,assign,copy,strong,weak
  10. hadoop的wordcount的改动版
  11. 使用SQL Server Management Studio 创建作业备份数据库
  12. Vue项目的部署
  13. iOS10 相册权限
  14. js或jquery实现点击某个按钮或元素显示div,点击页面其他任何地方隐藏div
  15. Chapter 5 Blood Type——7
  16. Spring Boot admin 2.0 详解
  17. maven wrapper使用本地maven
  18. makefile笔记2 - makefile总述
  19. PXE高效能批量网络装机
  20. 【模板】splay维护序列

热门文章

  1. 【HDOJ】1315 Basic
  2. tarjan缩点
  3. 【转】Android UI系列-----时间、日期、Toasts和进度条Dialog
  4. WEB/ WCF安全认证
  5. 模型-视图-控制器 (MVC)
  6. 限定checkbox最多选中数量
  7. 线段树求逆序数方法 HDU1394&amp;amp;&amp;amp;POJ2299
  8. winrar3.7-winrar4.0的注冊码
  9. ExtJS4.2学习(11)——高级组件之Grid
  10. Java基础知识强化47:StringBuffer类之StringBuffer的三个面试题