软件世界网 购物 网址 三丰软件 | 小说 美女秀 图库大全 游戏 笑话 | 下载 开发知识库 新闻 开发 图片素材
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
移动开发 架构设计 编程语言 Web前端 互联网
开发杂谈 系统运维 研发管理 数据库 云计算 Android开发资料
  软件世界网 -> 开发杂谈 -> hdu5365 -> 正文阅读
开发杂谈 最新文章
BloomFilter
大学四年编程之历程
内核分析
造人论坛——意识的本质和一个人工脑模型
OFDM信号[matlab描述]
人类还会进化吗?
HDUACM1035RobotMotion简单模拟题
树、二叉树(二)
iisphpweb.config处理404,500等,跳转友好
DatabaseAsaFortress

[开发杂谈]hdu5365

  2015-08-09 14:01:29

题目链接:点击打开链接
题目意思:在平面中给出一些点(这些点的坐标都为整数),从中选取一些点构成正三角形、正四边形、正五边形、正六边形,问一共有多少种方案?
解题思路:
1、题目给出的n<=20,而且题目中最多只构建到正六边形(由六个点组成),所以我们可以考虑暴力枚举
2、但是正五边形,正六边形判断起来感觉很麻烦,而且枚举6个点肯定会超时,所以比赛时没有思路
3、解题报告中指出:
地球人都知道整点是不能构成正五边形和正三边形和正六边形的,所以只需暴力枚举四个点判断是否是正四边形即可。假如你不是地球人,那么即使暴力枚举正三边形和稍微不那么暴力地找正五边形和正六边形也是可以通过的(反正找不到)。
看完题解,瞬间感觉自己弱爆了,看来e不是地球人呀。。。
所以直接暴力枚举正四边形也就是正方形喽(判定条件很多,选一个就行了,这里是菱形+一个直角)
#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
int n;
struct node{
    double x,y;
}d[30];
double getdis(node a,node b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool isequal(double x,double y){
    if(x-y>=-1e-8&&x-y<=1e-8)
        return true;
    return false;
}

bool isSquare(node a,node b,node c,node d){
    double len[6];
    len[0]=getdis(a,b);
    len[1]=getdis(a,c);
    len[2]=getdis(a,d);
    len[3]=getdis(b,c);
    len[4]=getdis(b,d);
    len[5]=getdis(c,d);
    double len1=len[0];
    double len2=len[0];
    for(int i=1;i<6;++i){
        if(!isequal(len[i],len2)&&!isequal(len[i],len1))
            len2=len[i];
    }
    for(int i=0;i<6;++i){
        if(isequal(len[i],len2)||isequal(len[i],len1));
        else return false;
    }
    if(len2-len1<-1e-8)
        swap(len1,len2);
    if(!isequal(2*len1*len1,len2*len2))
        return false;
    return true;
}


int main(){
    while(scanf("%d",&n)==1){
        long long ans=0;///不知道结果有多少种的情况下,直接longlong,防止溢出,当然本题是可以知道的
        for(int i=0;i<n;++i)
            scanf("%lf%lf",&d[i].x,&d[i].y);
        for(int i=0;i<n;++i)
            for(int j=i+1;j<n;++j)
                for(int u=j+1;u<n;++u)
                    for(int v=u+1;v<n;v++)
                        if(isSquare(d[i],d[j],d[u],d[v]))
                            ans++;
        printf("%I64d\n",ans);
    }
    return 0;
}

收获:
这几次比赛中都出现了类似这种题目的情况,题目给定的貌似很复杂,但很多经过所谓的常识筛选之后,就只剩下比较简单的情况了
类似题目hdu5277最大团问题,经过筛选后最大可能才四个点,直接暴力1、2、3、4个点就OK了
版权声明:本文为博主原创文章,未经博主允许不得转载。
上一篇文章      下一篇文章      查看所有文章
2015-08-09 14:01:02  
360图书馆 论文大全 母婴/育儿 软件开发资料 网页快照 文字转语音 购物精选 软件 美食菜谱 新闻中心 电影下载 小游戏 Chinese Culture
生肖星座解梦 人民的名义 人民的名义在线看 三沣玩客 拍拍 视频 开发 Android开发 站长 古典小说 网文精选 搜图网 天下美图
中国文化英文 多播视频 装修知识库
2017-4-25 3:07:42
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  软件世界网 --