软件世界网 购物 网址 三丰软件 | 小说 美女秀 图库大全 游戏 笑话 | 下载 开发知识库 新闻 开发 图片素材
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
移动开发 架构设计 编程语言 Web前端 互联网
开发杂谈 系统运维 研发管理 数据库 云计算 Android开发资料
  软件世界网 -> 开发杂谈 -> hdu5365 -> 正文阅读

[开发杂谈]hdu5365


题目链接:点击打开链接
题目意思:在平面中给出一些点(这些点的坐标都为整数),从中选取一些点构成正三角形、正四边形、正五边形、正六边形,问一共有多少种方案?
解题思路:
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  
开发杂谈 最新文章
BloomFilter
大学四年编程之历程
内核分析
造人论坛——意识的本质和一个人工脑模型
OFDM信号[matlab描述]
人类还会进化吗?
HDUACM1035RobotMotion简单模拟题
树、二叉树(二)
iisphpweb.config处理404,500等,跳转友好
DatabaseAsaFortress
360图书馆 软件开发资料 文字转语音 购物精选 软件下载 美食菜谱 新闻资讯 电影视频 小游戏 Chinese Culture 股票 租车
生肖星座 三丰软件 视频 开发 短信 中国文化 网文精选 搜图网 美图 阅读网 多播 租车 短信 看图 日历 万年历 2017年9日历
2017-9-24 16:50:23
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  软件世界网 --