BC 2015在百度之星程序设计大赛 - 预赛(1)(矩形区域-旋转卡)
2024-10-13 05:03:55
矩形区域
Accepts: 717
Submissions: 1619
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
Problem Description
小度熊有一个桌面,小度熊剪了非常多矩形放在桌面上。小度熊想知道能把这些矩形包围起来的面积最小的矩形的面积是多少。
Input
第一行一个正整数 T。代表測试数据组数(1≤T≤20 )。接下来
T 组測试数据。
每组測试数据占若干行,第一行一个正整数 N(1≤N<≤1000) ,代表矩形的数量。
接下来
N 行,每行 8 个整数x 1 ,y 1 ,x 2 ,y 2 ,x 3 ,y 3 ,x 4 ,y 4 ,代表矩形的四个点坐标,坐标绝对值不会超过10000。
Output
对于每组測试数据,输出两行:
第一行输出"Case #i:",i 代表第 i 组測试数据。 第二行包括1 个数字。代表面积最小的矩形的面积,结果保留到整数位。
Sample Input
2
2
5 10 5 8 3 10 3 8
8 8 8 6 7 8 7 6
1
0 0 2 2 2 0 0 2
Sample Output
Case #1:
17
Case #2:
4
旋转卡壳。和bzoj上那题基本同样
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])
#define MAXN (10000+10)
#define INF (1000000000)
#define eps 1e-6
struct P
{
double x,y;
P(){}
P(double _x,double _y):x(_x),y(_y){}
friend bool operator<(P a,P b){return (fabs(a.y-b.y)<eps)?a.x<b.x:a.y<b.y; }
friend bool operator==(P a,P b){return fabs(a.x-b.x)<eps&&fabs(a.y-b.y)<eps;}
friend bool operator!=(P a,P b){return !(a==b);} }a[MAXN],s[MAXN],ansp[5];
int size=0;
double ans=INF;
double dis2(P a,P b){return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}
struct V
{
double x,y;
V(){}
V(double _x,double _y):x(_x),y(_y){}
V(P a,P b):x(b.x-a.x),y(b.y-a.y){}
friend double operator*(V a,V b){return a.x*b.y-a.y*b.x;}
friend V operator*(double a,V b){return V(a*b.x,a*b.y);}
friend double operator/(V a,V b){return a.x*b.x+a.y*b.y;}
friend P operator+(P a,V b){return P(a.x+b.x,a.y+b.y);}
friend P operator-(P a,V b){return P(a.x-b.x,a.y-b.y);}
friend V operator~(V a){return V(a.y,-a.x);}
double dis2(){return x*x+y*y; }
};
int cmp(P A,P B)
{
double tmp=V(a[1],A)*V(a[1],B);
if (tmp>0) return 1;
else if (fabs(tmp)<eps) return (-dis2(A,a[1])-dis2(B,a[1])>0);
return 0;
}
int n; int main()
{
// freopen("F.in","r",stdin); int T;
cin>>T;
For(kcase,T)
{
ans=INF;
scanf("%d",&n);
n*=4;
for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);
for (int i=2;i<=n;i++) if (a[i]<a[1]) swap(a[1],a[i]);
sort(a+2,a+1+n,cmp);
s[1]=a[1];size=1;
for (int i=2;i<=n;)
if (size<2||V(s[size-1],s[size])*V(s[size],a[i])>eps) s[++size]=a[i++];
else size--;
s[0]=s[size]; int l=1,r=1,t=1;
for (int i=0;i<size;i++)
{
while (V(s[i],s[i+1])*V(s[i],s[t+1])-V(s[i],s[i+1])*V(s[i],s[t])>-eps) t=(t+1)%size;
while (V(s[i],s[i+1])/V(s[i],s[r+1])-V(s[i],s[i+1])/V(s[i],s[r])>-eps) r=(r+1)%size;
if (i==0) l=r;
while (V(s[i],s[i+1])/V(s[i],s[l+1])-V(s[i],s[i+1])/V(s[i],s[l])<eps) l=(l+1)%size;
double Dis2=dis2(s[i],s[i+1]),wlxdis=V(s[i],s[i+1])/V(s[i],s[l]),wrxdis=V(s[i],s[i+1])/V(s[i],s[r]),hxdis=V(s[i],s[i+1])*V(s[i],s[t]);
double tmp=hxdis*(wrxdis-wlxdis)/Dis2;
if (tmp<0) tmp=-tmp;
if (ans>tmp)
{
ans=tmp;
ansp[0]=s[i]-(wlxdis/Dis2)*V(s[i+1],s[i]);
ansp[1]=s[i]+(wrxdis/Dis2)*V(s[i],s[i+1]);
ansp[2]=ansp[1]+(hxdis/Dis2)*(~V(s[i+1],s[i]));
ansp[3]=ansp[0]+(hxdis/Dis2)*(~V(s[i+1],s[i]));
}
}
int p=0;
for (int i=1;i<4;i++) if (ansp[i]<ansp[p]) p=i;//p=0;
printf("Case #%d:\n",kcase);
printf("%.0lf\n",ans); }
return 0;
}
版权声明:本文博主原创文章,博客,未经同意,不得转载。
最新文章
- java中Action层、Service层和Dao层的功能区分
- PADS Layout 颜色设置
- *HDU3172 并查集
- Spire.Office组件使用例子
- 1o_Samba
- response设置输出文件编码
- Fiddler+Jmeter+断言详细教程
- Android Studio打包全攻略
- 【学习整理】NOIP涉及的数论 [updating]
- sessions 表的架构过程
- 大话数据结构—平衡二叉树(AVL树)
- C语言中的字符串拷贝函数strcpy和内存拷贝函数memcpy的区别与实现
- [GeekBand] 面向对象的设计模式(C++)(1)
- 《C#并行编程高级教程》第8章 线程池 笔记
- IPv6 tutorial 4 IPv6 address syntax
- UVA 10652 Board Wrapping(凸包)
- 初识google多语言通信框架gRPC系列(二)编译gRPC
- 加州理工大学公开课:机器学习与数据挖掘_线性模型 II(第IX类)
- Jmeter_24个常用函数(分享帖)
- Ansible playbook循环实践总结<;一>;
热门文章
- 【Java】运用JDBC实现一个注册、登录系统的编写
- 6.组函数(avg(),sum(),max(),min(),count())、多行函数,分组数据(group by,求各部门的平均工资),分组过滤(having和where),sql优化
- Revit 2015 公布!
- ECLIPSE JSP TOMCAT 环境搭建
- nginx subrequest演示示例程序
- DLNA它 Error, can&;#39;t findlibavformat ! 解
- 使用oracle数据库,多用户同时对一个表进行增加,删除,修改,查看等操作,会不会有影响?
- [ACM] POJ 3687 Labeling Balls (拓扑排序,反向生成端)
- 通过openssh远程登录时的延迟问题解决
- 使用dom4j创建和解析xml