题目链接:http://acm.timus.ru/problem.aspx?space=1&num=1043

题目大意:一个2000*2000方格坐标,x,y范围都是【-1000,1000】。现在给你一个圆弧,告诉你圆弧的两个端点和任意一个中间点。现在要你算出最小的矩形(长和宽都要为整数,即四个顶点在方格顶点上)来完全覆盖这个圆弧。

算法思路:很明显要算出圆心,这个可以有线段中垂线交求,也可以由方程,只是很麻烦。然后以圆心找出这个圆的左右上下四个极点,判断是否在圆弧上(用叉积即可),与给出的三个点一起维护这段圆弧的四个方向的极大点。然后向上向下取整即可。

代码:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std; const double eps = 1e-;
const double INF = 1000000000.00; struct Point{
double x,y;
Point(double x=,double y=): x(x), y(y) {}
}; typedef Point Vector; Vector operator + (Vector A,Vector B) { return Vector(A.x+B.x,A.y+B.y); }
Vector operator - (Vector A,Vector B) { return Vector(A.x-B.x,A.y-B.y); }
Vector operator * (Vector A,double p) { return Vector(A.x*p,A.y*p); }
Vector operator / (Vector A,double p) { return Vector(A.x/p,A.y/p); } bool operator < (const Point& A, const Point& B){
return A.x < B.x || (A.x == B.x && A.y < B.y);
}
int dcmp(double x){
if(fabs(x) < eps) return ;
return x < ? - : ;
}
bool operator == (const Point& A,const Point& B){
return dcmp(A.x-B.x) == && dcmp(A.y-B.y) == ;
}
double Dot(Vector A,Vector B){ return A.x*B.x+A.y*B.y; }
double Length(Vector A) { return sqrt(Dot(A,A)); }
double Cross(Vector A,Vector B) { return A.x*B.y-A.y*B.x; } Point read_point()
{
Point P;
scanf("%lf %lf",&P.x,&P.y);
return P;
}
Point normal(Vector A) { return Vector(-A.y,A.x); }; Point GetLineIntersecion(Point P, Vector v,Point Q,Vector w){
Vector u = P - Q;
double t = Cross(w,u)/Cross(v,w);
return P + v*t;
} void Judge(Point& Pl,Point& Pr,Point& Pu,Point& Pd,Point P){
if(Pl.x > P.x) Pl = P;
if(Pr.x < P.x) Pr = P;
if(Pu.y < P.y) Pu = P;
if(Pd.y > P.y) Pd = P;
} int main()
{
//freopen("E:\\acm\\input.txt","r",stdin);
Point Ps,Pt,Pi;
Ps = read_point();
Pt = read_point();
Pi = read_point();
Point mid1,mid2,O; mid1 = (Ps+Pi)/;
mid2 = (Pi+Pt)/;
O = GetLineIntersecion(mid1,normal(Ps-Pi),mid2,normal(Pi-Pt)); double r = Length(O-Ps);
Point Pu,Pl,Pr,Pd;
Pu = Pl = Pr = Pd = Ps; Judge(Pl,Pr,Pu,Pd,Pt);
Judge(Pl,Pr,Pu,Pd,Pi); Point P = Point(O.x+r,O.y);
if(dcmp(Cross(Pt-Ps,Pi-Ps)*Cross(Pt-Ps,P-Ps)) > ){
Judge(Pl,Pr,Pu,Pd,P);
}
P = Point(O.x-r,O.y);
if(dcmp(Cross(Pt-Ps,Pi-Ps)*Cross(Pt-Ps,P-Ps)) > ){
Judge(Pl,Pr,Pu,Pd,P);
}
P = Point(O.x,O.y+r);
if(dcmp(Cross(Pt-Ps,Pi-Ps)*Cross(Pt-Ps,P-Ps)) > ){
Judge(Pl,Pr,Pu,Pd,P);
}
P = Point(O.x,O.y-r);
if(dcmp(Cross(Pt-Ps,Pi-Ps)*Cross(Pt-Ps,P-Ps)) > ){
Judge(Pl,Pr,Pu,Pd,P);
}
int width = ceil(Pu.y-eps) - floor(Pd.y+eps);
int length = ceil(Pr.x-eps) - floor(Pl.x+eps);
printf("%d\n",width*length);
}

最新文章

  1. JAVA的反射理解
  2. htmlFormat
  3. 和为S的两个数字
  4. Android按键之Menu详解
  5. ExtJS笔记3 MVC Architecture
  6. 嵌入式linux
  7. 新手学习ios开发的辅助工具
  8. Android中常用适配器及定义自己的适配器
  9. 浅谈android4.0开发之GridLayout布局
  10. uva 11536 - Smallest Sub-Array
  11. Git联系oschina托管代码版本号
  12. sp_getAppLock使用
  13. hadoop分布式搭建
  14. ok6410如何从sdram中启动uboot 调试 这是一个猜想还没有验证
  15. HTTP协议转码
  16. mobile adaptor &amp; css media query
  17. nodejs之querystring(查询字符串)
  18. matlab中输入x. 与x的区别
  19. 使用gitlab, jenkins搭建CI(持续集成)系统(4) 灰度发布publish
  20. 成功让Eclipse更新ADT的方法

热门文章

  1. Script: Who’s using a database link?(找出谁在使用dblink)
  2. 应用程序中小红点设置方法 (ios)
  3. LINQ 101——约束、投影、排序
  4. ios专题 -归档保存数据
  5. struts2 测试错题解析
  6. Windows phone 之常用控件
  7. 获得SQLSERVER的表字段等架构信息
  8. mount的艺术
  9. 虚拟化技术与&quot;云&quot;
  10. 【转】Eclipse工具使用技巧总结