首页 > 代码库 > bzoj-2338 2338: [HNOI2011]数矩形(计算几何)
bzoj-2338 2338: [HNOI2011]数矩形(计算几何)
题目链接：
2338: [HNOI2011]数矩形
Description
Input
Output
题意：
思路：
求最大的矩形面积,先把这些点转化成线段,记录下线段的长度和中点和两个端点,形成矩形说明对角线长度相等,且共中点,所以把线段按长度和中点排序,如果都相等,然后用三角形的三个顶点坐标计算面积的公式计算最大面积就好了;
AC代码：
/************************************************************** Problem: 2338 User: LittlePointer Language: C++ Result: Accepted Time:5172 ms Memory:73520 kb****************************************************************/ #include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <bits/stdc++.h>#include <stack>#include <map> using namespace std; #define For(i,j,n) for(int i=j;i<=n;i++)#define mst(ss,b) memset(ss,b,sizeof(ss)); typedef long long LL; template<class T> void read(T&num) { char CH; bool F=false; for(CH=getchar();CH<‘0‘||CH>‘9‘;F= CH==‘-‘,CH=getchar()); for(num=0;CH>=‘0‘&&CH<=‘9‘;num=num*10+CH-‘0‘,CH=getchar()); F && (num=-num);}int stk[70], tp;template<class T> inline void print(T p) { if(!p) { puts("0"); return; } while(p) stk[++ tp] = p%10, p/=10; while(tp) putchar(stk[tp--] + ‘0‘); putchar(‘\n‘);} const LL mod=1e9+7;const double PI=acos(-1.0);const int inf=1e9;const int N=4e5+10;const int maxn=1e3+520;const double eps=1e-12; struct PO{ LL x,y;}po[maxn];struct Seg{ PO m; int s,e; LL dist;}seg[maxn*maxn];inline LL dis(int a,int b){ return (po[a].x-po[b].x)*(po[a].x-po[b].x)+(po[a].y-po[b].y)*(po[a].y-po[b].y);}int cmp(Seg a,Seg b){ if(a.dist==b.dist) { if(a.m.x==b.m.x)return a.m.y<b.m.y; return a.m.x<b.m.x; } return a.dist<b.dist;}inline LL getans(int a,int b,int c){ LL sum=po[a].x*po[b].y+po[b].x*po[c].y+po[c].x*po[a].y; sum=sum-po[a].x*po[c].y-po[b].x*po[a].y-po[c].x*po[b].y; if(sum<0)return -sum; return sum;}inline LL solve(int temp,int f){ return getans(seg[temp].s,seg[temp].e,seg[f].s);}int main(){ int n; read(n); For(i,1,n) { read(po[i].x); read(po[i].y); } int cnt=0; for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) { cnt++; seg[cnt].s=i; seg[cnt].e=j; seg[cnt].m.x=po[i].x+po[j].x; seg[cnt].m.y=po[i].y+po[j].y; seg[cnt].dist=dis(i,j); } } sort(seg,seg+cnt+1,cmp); LL ans=0; for(int i=1;i<=cnt;i++) { for(int j=i+1;;j++) { if(seg[j].dist==seg[i].dist&&seg[j].m.x==seg[i].m.x&&seg[j].m.y==seg[i].m.y)ans=max(ans,solve(j,i)); else break; } } cout<<ans<<"\n"; return 0;}
bzoj-2338 2338: [HNOI2011]数矩形(计算几何)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。