Squares UVALive - 4728

Squares UVALive - 4728

题意 求多边形的直径（及距离最远的两点的距离）
1. 首先求凸包，因为所求的最远的两个点肯定是凸包上的点
2. 取最下面点 Pi $P_i$和最上面的点 Pj $P_j$为对踵点（对踵点，以这一点做两平行直线可以包含整个凸包，距离最远的两个点必为对踵点）
3. 然后以 Pi $P_i$做水平向右的射线，以 Pj $P_j$做水平向左的射线，逆时针旋转
4. 旋转相同的角度时假设射线 Pi $P_i$先贴合线段 Pi−Pi+1, $P_i-P_{i+1},$,,则 Pi+1 $P_{i+1}$和 Pj $P_j$也为对踵点
5.如果同时贴合，则这四个点都互为对踵点
6.求这些对踵点的距离平方最大值即为所求

#include<bits/stdc++.h>
#define f(a,b) ((a%b+b)%b)
const double eps = 1e-10;
const double pi = acos(-1.0);
//......................................................
using namespace std;
struct Point
{
// Point() = default;
    double x,y;
    Point(double x = 0,double y = 0):x(x),y(y),xx(x),yy(y) {}
    int  xx,yy;
};
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);
}
int dcmp(double x)
{
    if(fabs(x)<eps)
        return 0;
    else
        return x < 0?-1:1;
}
bool operator < (const Point &a,const Point &b)
{
    if(dcmp(a.x-b.x)==0)
        return a.y<b.y;
    else
        return a.x<b.x;
}
double Length(Vector A)
{
    return sqrt(A.x*A.x+A.y*A.y);
}
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 Angle(Vector A,Vector B)
{
    return acos(Dot(A,B)/Length(A)/Length(B));
}
double Cross(Vector A,Vector B)
{
    return A.x*B.y - A.y*B.x;
}
//---------------------------+
//计算凸包，输入点数组p,个数为p，输出点数组为ch。函数返回凸包顶点数
//输入不能有重复节点
//如果精度要求搞需要用dcmp判断
//如果不希望在边上右点，需要将 <= 改为 <
int ConvexHull (Point *p,int n,Point *ch)
{
    sort(p,p+n);
    int m = 0;
    for(int i = 0; i < n; ++i)
    {
        while(m>1&& dcmp(Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2]))<=0)
            m--;
        ch[m++] = p[i];

    }
    int k = m;
    for(int i = n-2; i >= 0; --i)
    {
        while(m > k&& dcmp(Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])) <= 0)
            m--;
        ch[m++] = p[i];
    }
    if(n > 1)
        m--;
    return m;
}
int  square(Vector a)
{
    return a.xx*a.xx + a.yy*a.yy;
}
const int maxn = 1e5+10;
Point P[maxn*4],ch[maxn*4];
int main(void)
{
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        for(int i = 0; i < n; ++i)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            P[4*i] = Point(x,y);
            P[4*i+1] = Point(x+z,y);
            P[4*i+2] = Point(x+z,y+z);
            P[4*i+3] = Point(x,y+z);
        }//正方形的四个顶点
        int m = ConvexHull(P,n*4,ch);//求凸包
        ch[m] = ch[0]; //省下取模的步骤
        double Max = ch[0].y,Min = ch[0].y;//求最上和最下点
        int Index_Min = 0,Index_Max = 0;
        for(int i = 0; i < m; ++i)
        {
            if(Max<ch[i].y)
            {
                Max = ch[i].y;
                Index_Max = i;
            }
            if(Min>ch[i].y)
            {
                Min = ch[i].y;
                Index_Min = i;
            }
        }

        int a = Index_Min,b = Index_Max;
        int  Ans = 0;
        double rad1 = 0,rad2 = 0 ;
        rad1 = Angle(Point(1,0),ch[(a+1)%m]-ch[a]);//由两条射线旋转到下一个线段需要旋转的度数
        rad2 = Angle(Point(-1,0),ch[(b+1)%m]-ch[b]);
        double sumrad1;//总旋转度数
        sumrad1 =  0;
        while(dcmp(sumrad1 - pi) <= 0)//总旋转度数大于pi时停止旋转
        {
            if(a!=Index_Min&&dcmp(rad1)<=0)
                rad1 = Angle(ch[a]-ch[f(a-1,m)],ch[f(a+1,m)]-ch[a]);
            if(b!=Index_Max&&dcmp(rad2)<=0)
                rad2 = Angle(ch[b]-ch[f(b-1,m)],ch[f(b+1,m)]-ch[b]);
            int tmp = dcmp(rad1-rad2);
            if(tmp > 0)
                sumrad1 += rad2,rad1 -= rad2,rad2 = 0,b++;
            else if(tmp == 0)
                sumrad1 += rad1,rad1 = rad2 = 0,a++,b++;
            else
                sumrad1 += rad1,rad2 -= rad1,rad1 = 0,a++;

            Ans = max(Ans,square(ch[f(a,m)]-ch[f(b-1,m)]));
            Ans = max(Ans,square(ch[f(a,m)]-ch[f(b,m)]));
            a %= m;
            b %= m;
        }
        cout<<Ans<<endl;

    }



    return 0;
}

刘汝佳代码仓库中解题代码

// LA4728/UVa1453 Square
// Rujia Liu
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;

struct Point {
  int x, y;
  Point(int x=0, int y=0):x(x),y(y) { }
};

typedef Point Vector;

Vector operator - (const Point& A, const Point& B) {
  return Vector(A.x-B.x, A.y-B.y);
}

int Cross(const Vector& A, const Vector& B) {
  return A.x*B.y - A.y*B.x;
}

int Dot(const Vector& A, const Vector& B) {
  return A.x*B.x + A.y*B.y;
}

int Dist2(const Point& A, const Point& B) {
  return (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y);
}

bool operator < (const Point& p1, const Point& p2) {
  return p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y);
}

bool operator == (const Point& p1, const Point& p2) {
  return p1.x == p2.x && p1.y == p2.y;
}

// 点集凸包
// 如果不希望在凸包的边上有输入点，把两个 <= 改成 <
// 注意：输入点***被修改
vector<Point> ConvexHull(vector<Point>& p) {
  // 预处理，删除重复点
  sort(p.begin(), p.end());
  p.erase(unique(p.begin(), p.end()), p.end());

  int n = p.size();
  int m = 0;
  vector<Point> ch(n+1);
  for(int i = 0; i < n; i++) {
    while(m > 1 && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--;
    ch[m++] = p[i];
  }
  int k = m;
  for(int i = n-2; i >= 0; i--) {
    while(m > k && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--;
    ch[m++] = p[i];
  }
  if(n > 1) m--;
  ch.resize(m);
  return ch;
}

// 返回点集直径的平方
int diameter2(vector<Point>& points) {
  vector<Point> p = ConvexHull(points);
  int n = p.size();
  if(n == 1) return 0;
  if(n == 2) return Dist2(p[0], p[1]);
  p.push_back(p[0]); // 免得取模
  int ans = 0;
  for(int u = 0, v = 1; u < n; u++) {
    // 一条直线贴住边p[u]-p[u+1]
    for(;;) {
      // 当Area(p[u], p[u+1], p[v+1]) <= Area(p[u], p[u+1], p[v])时停止旋转
      // 即Cross(p[u+1]-p[u], p[v+1]-p[u]) - Cross(p[u+1]-p[u], p[v]-p[u]) <= 0
      // 根据Cross(A,B) - Cross(A,C) = Cross(A,B-C)
      // 化简得Cross(p[u+1]-p[u], p[v+1]-p[v]) <= 0
      int diff = Cross(p[u+1]-p[u], p[v+1]-p[v]);
      if(diff <= 0) {
        ans = max(ans, Dist2(p[u], p[v])); // u和v是对踵点
        if(diff == 0) ans = max(ans, Dist2(p[u], p[v+1])); // diff == 0时u和v+1也是对踵点
        break;
      }
      v = (v + 1) % n;
    }
  }
  return ans;
}

int main() {
  int T;
  scanf("%d", &T);
  while(T--) {
    int n;
    scanf("%d", &n);
    vector<Point> points;
    for(int i = 0; i < n; i++) {
      int x, y, w;
      scanf("%d%d%d", &x, &y, &w);
      points.push_back(Point(x, y));
      points.push_back(Point(x+w, y));
      points.push_back(Point(x, y+w));
      points.push_back(Point(x+w, y+w));
    }
    printf("%d\n", diameter2(points));
  }
  return 0;
}