POJ - 1266 -

题目大意：给出一条圆弧上的两个端点A,B，和圆弧上两端点之间的一个点C，现在要用一块各个定点的坐标均为整数的矩形去覆盖这个圆弧，要求最小的矩形面积。

思路：叉积在本体发挥很强大的作用。首先求出三个点所在圆的圆心，也就是三角形的外心，然后判断着个圆上最上，最下，最左，最右四个点是否在该圆弧上，如果在，那么所求矩形的最上，最下，最左，最右边的坐标就是对应的点的坐标，否则，应该有圆弧两端点的坐标的相对大小来确定！

要判断一个点是否在圆弧上，主要用到叉积！把AB连结起来，设待检测的点式P，则如果是p在圆弧上，那么点p和点C在直线AB 的同一侧，否则在异侧，所以可由叉积判断！

#include <iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<stdlib.h>

#include<vector>

#include<cmath>

#include<queue>

#include<set>

  using namespace std;

  #define N 100000

  #define LL long long

  #define INF 0xfffffff

  const double eps = 1e-;

  const double pi = acos(-1.0);

 const double inf = ~0u>>;

  struct Point

 {

      double x,y;

      Point(double x=,double y=):x(x),y(y) {}

  }p[];

  typedef Point pointt;

  pointt operator + (Point a,Point b)

  {

       return Point(a.x+b.x,a.y+b.y);

  }

  pointt operator - (Point a,Point b)

  {

         return Point(a.x-b.x,a.y-b.y);

  }

  int dcmp(double x)

  {

      if(fabs(x)<eps) return ;

      else return x<?-:;

  }

  struct Circle

  {

      Point center;

      double r;

  };

  double cross(Point a,Point b)

  {

      return a.x*b.y-a.y*b.x;

  }

  double mul(Point p0,Point p1,Point p2)

  {

      return cross(p1-p0,p2-p0);

  }

  double dis(Point a)

  {

      return a.x*a.x+a.y*a.y;

 }

  double area()

 {

      return fabs(cross(p[]-p[],p[]-p[]))/;

  }

  bool seginter(pointt a1,pointt a2,pointt b1,pointt b2)

  {

       double c1 = cross(a2-a1,b1-a1),c2 = cross(a2-a1,b2-a1),

              c3 = cross(b2-b1,a1-b1),c4 = cross(b2-b1,a2-b1);

       return dcmp(c1)*dcmp(c2)<&&dcmp(c3)*dcmp(c4)<;

  }

  struct Circle Circumcircle()

 {

      Circle tmp;

      double a,b,c,c1,c2;

     double xa,ya,xb,yb,xc,yc;

      a = sqrt(dis(p[]-p[]));

      b = sqrt(dis(p[]-p[]));

      c = sqrt(dis(p[]-p[]));

     tmp.r = (a*b*c)/(area()*4.0);

      xa = p[].x;

      ya = p[].y;

      xb = p[].x;

      yb = p[].y;

     xc = p[].x;

      yc = p[].y;

      c1 = (dis(p[])-dis(p[]))/;

      c2 = (dis(p[])-dis(p[]))/;

      tmp.center.x = (c1*(ya-yc)-c2*(ya-yb))/((xa-xb)*(ya-yc)-(xa-xc)*(ya-yb));

     tmp.center.y = (c1*(xa-xc)-c2*(xa-xb))/((ya-yb)*(xa-xc)-(ya-yc)*(xa-xb));

      return tmp;

  }

  int main()

  {

     int i;

      double r;

      int w0,w1,h0,h1;

      for(i = ; i <=  ; i++)

      scanf("%lf%lf",&p[i].x,&p[i].y);

      Circle cc = Circumcircle();

      r = cc.r;

      Point q[];

      for(i =  ;i <  ;i++)

     q[i] = cc.center;

      q[].x-=r,q[].x+=r,q[].y-=r,q[].y+=r;

    if(!seginter(q[],p[],p[],p[])) w0 = floor(q[].x+eps);

     else w0 = floor(min(p[].x,p[].x)+eps);

     if(!seginter(q[],p[],p[],p[]))  w1 = ceil(q[].x-eps);

    else w1 = ceil(max(p[].x,p[].x)-eps);

     if(!seginter(q[],p[],p[],p[])) h0 = floor(q[].y+eps);

     else h0 = floor(min(p[].y,p[].y)+eps);

     if(!seginter(q[],p[],p[],p[])) h1 = ceil(q[].y-eps);

     else h1 = ceil(max(p[].y,p[].y)-eps);

     printf("%d\n",(h1-h0)*(w1-w0));

     return ;

 }

巴特西

POJ - 1266 -

最新文章

热门文章