HDU 1249 三角形(三角形分割平面)
2024-08-27 08:07:15
传送门:
http://acm.hdu.edu.cn/showproblem.php?pid=1249
三角形
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 9065 Accepted Submission(s): 5946
Problem Description
用N个三角形最多可以把平面分成几个区域?
Input
输入数据的第一行是一个正整数T(1<=T<=10000),表示测试数据的数量.然后是T组测试数据,每组测试数据只包含一个正整数N(1<=N<=10000).
Output
对于每组测试数据,请输出题目中要求的结果.
Sample Input
2
1
2
1
2
Sample Output
2
8
8
Author
Ignatius.L
分析:
两种分析方法:
第一种:
可以画一个圆,圆里放一个内正三角形。当放入第二个时,我们就把它转化为把已有的第一个三角形围着同心
轴稍微往右转一点点(向左转一样的),那么,第二个三角形的每一条边都会与第一个三角形的其中两条边相交
,这样就可得3*1*2+2个区域,3表示3条边,1表示第二个三角形的每一条边都会与第一个三角形的其中两条边相
交后得到一个三角形,2表示2个三角形,+2则表示外面的区域和同有的2个三角形共有的一个区域。同样第三个
三角形会与第一第二个三角形都有两条边相交。可得:3*2*3+2
由些可得,n个三角形:3*(n-1)*n+2
轴稍微往右转一点点(向左转一样的),那么,第二个三角形的每一条边都会与第一个三角形的其中两条边相交
,这样就可得3*1*2+2个区域,3表示3条边,1表示第二个三角形的每一条边都会与第一个三角形的其中两条边相
交后得到一个三角形,2表示2个三角形,+2则表示外面的区域和同有的2个三角形共有的一个区域。同样第三个
三角形会与第一第二个三角形都有两条边相交。可得:3*2*3+2
由些可得,n个三角形:3*(n-1)*n+2
第二种:
我们知道,对于第i个三角形来说,其前面已经有了(i-1)个三角形==>有(3i-3)条边,对于第i个
三角形,其每一条边最多能和之前的每个三角形的2条边有交点,即能和前面的(2i-2)条边各有
一个交点,而这些交点会把第i个三角形的一条边分割成(2i-1)条线段,每一条线段会增加一个平面,这样3条边就增加了(2i-1)×3个平面,考虑到在三角形的三个顶点,在每一个顶点处相邻的两个线段并不会增加平面的数目,所以在三个顶点处的6个线段实质上只增加了3个平面,所以要减去这3个多算的平面数,这样,第i个三角形就会比i-1个三角形形成的平面数多出(2i-1)×3-3=6(i-1)个了,即递推关系为:f(n)=f(n-1)+6×(i-1)。
code:
#include<bits/stdc++.h>
using namespace std;
#define max_v 10010
int main()
{
int a[max_v];
a[]=;
a[]=;
for(int i=;i<max_v;i++)
{
a[i]=a[i-]+*(i-);
}
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
printf("%d\n",a[n]);
}
return ;
}
最新文章
- mybatis Generator生成代码及使用方式
- SSH 端口转发+内网穿透
- codeforces E. Famil Door and Roads 期望
- phpstorm内网远程debug
- HTTP协议状态码详解(HTTP Status Code)
- (转)SQL server 容易让人误解的问题之 聚集表的物理顺序问题
- ZOJ2006 (后缀自动机)
- springMVC+jpa配置之简单案例
- 用PHP对数据库数据进行删除
- Hive QL
- 牛顿迭代法实现平方根函数sqrt
- MongoDB 覆盖索引查询
- Linux下Shadow socks的安装和配置
- 04-PHP-redis
- 正则表达式(Regular expressions)使用笔记
- QTableWidgetItem class
- 利用Selenium爬取淘宝商品信息
- 微信小程序之自定义模态弹窗(带动画)实例
- 文件压缩:zip
- 实验long raw 和 blob两种数据类型遇到dblink的表现