关于三分的暴力技巧
以下为暴力专场()
现在以hdu4454为例
1.这道题的一个总结点是暴力对于精度不超过1e-2的东西,我们可以直接暴力求解
2.几何:对于一个圆()都需要掌握三角函数的运用,这里有一篇非常不错的文章可以学习
3.圆到矩形的最短距离
关于圆到矩形的最短距离,主要是关于是到
现在附上超级牛逼的暴力代码(感谢qt)
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdlib>
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch))
{
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return x*f;
}
inline void out()
{
fclose(stdin);
fclose(stdout);
}
const double pi=acos(-1.0);
struct Point{
double x,y,r;
}C,P,st;
double xx,yy,x2,y2,miny,maxy,minx,maxx;
inline double dist(Point a,Point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
inline double Rdist(Point a)
{
double x=0.0,y=0.0;
if(a.x<minx) x=minx-a.x;
else if(a.x>maxx) x=a.x-maxx;
if(a.y<miny) y=miny-a.y;
else if(a.y>maxy) y=a.y-maxy;
return sqrt(x*x+y*y);
}
int main(void)
{
while(1)
{
scanf("%lf%lf",&st.x,&st.y);
if(st.x==0&&st.y==0) break;
double ans=1e10;
scanf("%lf%lf%lf",&C.x,&C.y,&C.r);
scanf("%lf%lf%lf%lf",&xx,&yy,&x2,&y2);
minx=min(xx,x2),maxx=max(xx,x2);
miny=min(yy,y2),maxy=max(yy,y2);
for(double rad=0;rad<=360;rad+=0.005)
{
Point P;
P.x=C.x+C.r*cos(rad/180*pi);
P.y=C.y+C.r*sin(rad/180*pi);
ans=min(ans,dist(P,st)+Rdist(P));
}
printf("%.2f\n",ans);
}
out();
return 0;
}
还有正解()
#include<algorithm>
#include<iostream>
#include<fstream>
#include<sstream>
#include<cstring>
#include<cstdlib>
#include<string>
#include<vector>
#include<cstdio>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<set>
#define FF(i, a, b) for(int i=a; i<b; i++)
#define FD(i, a, b) for(int i=a; i>=b; i--)
#define REP(i, n) for(int i=0; i<n; i++)
#define CLR(a, b) memset(a, b, sizeof(a))
#define LL long long
#define PB push_back
#define eps 1e-10
#define debug puts("**debug**");
using namespace std;
const double PI = acos(-1);
struct Point
{
double x, y;
Point(double x=0, double y=0):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 0; return x < 0 ? -1 : 1;
}
bool operator == (const Point& a, const Point& b)
{
return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) == 0;
}
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; }
double DistanceToSegment(Point p, Point a, Point b)
{
if(a == b) return Length(p-a);
Vector v1 = b-a, v2 = p-a, v3 = p-b;
if(dcmp(Dot(v1, v2)) < 0) return Length(v2);
else if(dcmp(Dot(v1, v3)) > 0) return Length(v3);
else return fabs(Cross(v1, v2)) / Length(v1);
}
struct Circle
{
Point c;
double r;
Circle(){}
Circle(Point c, double r):c(c), r(r){}
Point point(double a) //根据圆心角求点坐标
{
return Point(c.x+cos(a)*r, c.y+sin(a)*r);
}
}o;
Point p, p1, p2, p3, p4, s;
double a, b, c, d;
double Calc(double x)
{
p = o.point(x);
double d1 = DistanceToSegment(p, p1, p2),
d2 = DistanceToSegment(p, p2, p3),
d3 = DistanceToSegment(p, p3, p4),
d4 = DistanceToSegment(p, p4, p1);
//点p到矩形最近距离加上s到p距离
return min(min(d1, d2), min(d3, d4)) + Length(s-p);
}
double solve()
{
double L, R, m, mm, mv, mmv;
L = 0; R = PI;
while (L + eps < R)
{
m = (L + R) / 2;
mm = (m + R) / 2;
mv = Calc(m);
mmv = Calc(mm);
if (mv <= mmv) R = mm; //三分法求最大值时改为mv>=mmv
else L = m;
}
double ret = Calc(L);
L = PI; R = 2*PI;
while (L + eps < R)
{
m = (L + R) / 2;
mm = (m + R) / 2;
mv = Calc(m);
mmv = Calc(mm);
if (mv <= mmv) R = mm;
else L = m;
}
return min(ret, Calc(L));
}
int main()
{
while(scanf("%lf%lf", &s.x, &s.y))
{
if(s.x == 0 && s.y == 0) break;
scanf("%lf%lf%lf", &o.c.x, &o.c.y, &o.r);
scanf("%lf%lf%lf%lf", &a, &b, &c, &d);
//确定矩形四个点坐标,左上点开始 逆时针
double maxx, maxy, minx, miny;
maxx = max(a, c); maxy = max(b, d);
minx = min(a, c); miny = min(b, d);
p1 = Point(minx, maxy);
p2 = Point(minx, miny);
p3 = Point(maxx, miny);
p4 = Point(maxx, maxy);
double ans = solve();
printf("%.2f\n", ans);
}
return 0;
}