注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ2338][HNOI2011]数矩形  

2014-12-16 09:00:33|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2338: [HNOI2011]数矩形

卧槽被卡精度了……
没有必要的开方,一定要除法全部舍去
题解在代码下方

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
const int N = 1500+10;
int n,m;
struct Point{
int x,y;
Point(){}
Point(int aa,int bb):x(aa),y(bb){}
void print(){
printf("%d %d\n",x,y);
}
}point[N];
Point operator + (Point a,Point b){return Point(a.x+b.x,a.y+b.y);}
struct Line{
int p[2];Point cent;long long len;
}lines[N*N];int ln;
bool operator < (Point a,Point b){return a.x==b.x?a.y<b.y:a.x < b.x;}
bool operator == (Point a,Point b){return a.x==b.x&&a.y==b.y;}
bool dcmp(double a,double b){return fabs(a-b) < 1e-9;}
bool operator < (const Line &a,const Line &b){
if(!(a.cent==b.cent))return a.cent < b.cent;
return a.len < b.len;
}
bool operator == (Line &a,Line &b){return a.len==b.len && a.cent == b.cent;}
Point operator - (Point a,Point b){return Point(a.x-b.x,a.y-b.y);}
double cross(Point a,Point b){return (double)a.x*b.y-(double)a.y*b.x;}
double dis(Point a,Point b){return hypot(a.x-b.x,a.y-b.y);}
int scan(){int i=0;scanf("%d",&i);return i;}
int main(){
//freopen("input.txt","r",stdin);
int i,j,a,b,c;
n = scan();
for(i=1;i<=n;i++){
a = scan();b = scan();
point[i] = Point(a,b);
}
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++){
ln++;
lines[ln].p[0] = i;lines[ln].p[1] = j;
lines[ln].cent = point[i] + point[j];
//cout << lines[ln].cent.x << ' '<<lines[ln].cent.y<<endl;
long long tmp[2];
tmp[0] = point[i].x-point[j].x;
tmp[1] = point[i].y-point[j].y;
//lines[ln].len = hypot(point[i].x-point[j].x,point[i].y-point[j].y);
lines[ln].len = tmp[0]*tmp[0]+tmp[1]*tmp[1];;
}
sort(lines+1,lines+1+ln);
double ans = 0;
for(i=1;i<ln;i++)
for(j=i+1;j<=ln;j++)
if(lines[i]==lines[j]){
//printf("%f\n",lines[i].len);
double tmp[2];
a = lines[i].p[0];b = lines[i].p[1];
c = lines[j].p[0];
tmp[0] = cross(point[a]-point[c],point[b]-point[c]);
if(tmp[0]<0)tmp[0]=-tmp[0];
if(tmp[0] > ans){
ans = tmp[0];
}
}else break;
printf("%.0f\n",ans+1e-9);
return 0;
}

题解:
首先枚举出所有的线,然后两条线作为对角线可以构成矩形的条件是这两条线中点相同,并且长度相同。
因为线是由枚举点对得到的,所以相互间可以构成矩形的合法情况不会太多,直接排序之后暴力。
最好都用int,long long存,要不就用long double,只用double 会被卡精度。
面积最好用叉积,算线长度和中点的时候不要开方/除2
  评论这张
 
阅读(42)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017