【Codeforces】J. Polygons Intersection 两个凸多边形交的面积

文章目录

• • 问题
  • Code
  • 测例
  • Accepted 代码：

问题

假设恰有两个多边形，它们都是凸的，其顶点以逆时针顺序给出，并且具有非零区域。此外，在一个多边形中，顶点不会在另一个多边形的两侧。如下图所示：

Code

#include <iostream>
#include <vector>
#include <math.h> 
using namespace std;

const double FLOAT_EPS = 1e-10;

class Point
{
/**
  * Point coordinate information
  */
    public:
        Point(const double x = 0, const double y = 0, const double z = 0):_x(x), _y(y) {}
        Point(const Point& p) : _x( p.getX() ), _y( p.getY() ) {;}
        ~Point() {}
        const double getX() const {return _x;}
        const double getY() const {return _y;}
        void setX(const double x) {_x = x;}
        void setY(const double y) {_y = y;}
        
    private:
        double _x, _y;
};


double cross(const Point& p, const Point& q, const Point& r)
{
  return (p.getX() - q.getX()) * (r.getY() - q.getY()) -
         (p.getY() - q.getY()) * (r.getX() - q.getX());
}
 
// line segment p-q intersect with line A-B
void lineIntersectSeg(const Point& p, const Point& q, const Point& A, const Point& B, Point& res)
{
  double a = B.getY() - A.getY();
  double b = A.getX() - B.getX();
  double c = B.getX() * A.getY() - A.getX() * B.getY();
  double u = fabs(a * p.getX() + b * p.getY() + c);
  double v = fabs(a * q.getX() + b * q.getY() + c);
  res.setX((p.getX()*v + q.getX()*u)/(u+v));
  res.setY((p.getY()*v + q.getY()*u)/(u+v));
}

void cutPolygon(const Point& a, const Point& b, const vector<Point>& Q, vector<Point>& res)
{
  
  for(unsigned int i = 0; i < Q.size(); i++)
  {
      double left1 = cross(a, b, Q[i]), left2 = 0.0;
      if(i != (int)Q.size()-1) {
        left2 = cross(a, b, Q[i+1]);
      }
      if(left1 > -FLOAT_EPS) {
        res.push_back(Q[i]);
      }
      if(left1 * left2 < -FLOAT_EPS) {
        Point p(0.0, 0.0);
        lineIntersectSeg(Q[i], Q[i+1], a, b, p);
        res.push_back(p);
      }
  }
 
  if(res.empty()) {
    return ;
  }
  if(fabs(res.back().getX() - res.front().getX()) > FLOAT_EPS || fabs(res.back().getY() - res.front().getY()) > FLOAT_EPS) {
    res.push_back(res.front());
  }
}

double area(const vector<Point> & pts)
{
  if(pts.empty()) {
    return 0.0;
  }
  double result = 0.0;
  for(unsigned int i = 0; i< pts.size()-1; ++i) {
    result += (pts[i].getX() * pts[i+1].getY() - pts[i].getY() * pts[i+1].getX());
  }
  return fabs(result)/2.0;
}

double intersectArea(const vector<Point>& polys1, const vector<Point>& polys2)
{
    vector<Point> pts1 = polys1;
    vector<Point> pts2 = polys2;
    pts1.push_back(pts1[0]);
    pts2.push_back(pts2[0]);
    vector<Point> res;
    for(unsigned int i = 0; i < polys2.size(); ++i) {
        res.clear();
        cutPolygon(pts2[i + 1], pts2[i], pts1, res);
        pts1 = res;
    }
    return area(res);
}

           

测例

可以参考网址 ：Condeforces-J

Input

The first line of the input will be a single integer T, the number of test cases (1  ≤  T  ≤  20). each test case contains two integers (3  ≤  N, M  ≤  40) Then a line contains N pairs of integers xi, yi (-1000  ≤  xi, yi  ≤  1000) coordinates of the ith vertex of polygon A, followed by a line contains M pairs of integers xj, yj (-1000  ≤  xj, yj  ≤  1000) coordinates of the jth vertex of polygon B. The coordinates are separated by a single space.

Output

For each test case, print on a single line, a single number representing the area of intersection, rounded to four decimal places.

Examples

input

2

5 3

0 3 1 1 3 1 3 5 1 5

1 3 5 3 3 6

3 3

-1 -1 -2 -1 -1 -2

1 1 2 1 1 2

output

2.6667

0.0000

Accepted 代码：

#include <iostream>
#include <vector>
#include <math.h> 
using namespace std;

const double FLOAT_EPS = 1e-10;


class Point
{
/**
  * Point coordinate information
  */
    public:
        Point(const double x = 0, const double y = 0, const double z = 0):_x(x), _y(y) {}
        Point(const Point& p) : _x( p.getX() ), _y( p.getY() ) {;}
        ~Point() {}
        const double getX() const {return _x;}
        const double getY() const {return _y;}
        void setX(const double x) {_x = x;}
        void setY(const double y) {_y = y;}
        
    private:
        double _x, _y;
};


double cross(const Point& p, const Point& q, const Point& r)
{
  return (p.getX() - q.getX()) * (r.getY() - q.getY()) -
         (p.getY() - q.getY()) * (r.getX() - q.getX());
}
 
// line segment p-q intersect with line A-B
void lineIntersectSeg(const Point& p, const Point& q, const Point& A, const Point& B, Point& res)
{
  double a = B.getY() - A.getY();
  double b = A.getX() - B.getX();
  double c = B.getX() * A.getY() - A.getX() * B.getY();
  double u = fabs(a * p.getX() + b * p.getY() + c);
  double v = fabs(a * q.getX() + b * q.getY() + c);
  res.setX((p.getX()*v + q.getX()*u)/(u+v));
  res.setY((p.getY()*v + q.getY()*u)/(u+v));
}

void cutPolygon(const Point& a, const Point& b, const vector<Point>& Q, vector<Point>& res)
{
  
  for(unsigned int i = 0; i < Q.size(); i++)
  {
      double left1 = cross(a, b, Q[i]), left2 = 0.0;
      if(i != (int)Q.size()-1) {
        left2 = cross(a, b, Q[i+1]);
      }
      if(left1 > -FLOAT_EPS) {
        res.push_back(Q[i]);
      }
      if(left1 * left2 < -FLOAT_EPS) {
        Point p(0.0, 0.0);
        lineIntersectSeg(Q[i], Q[i+1], a, b, p);
        res.push_back(p);
      }
  }
 
  if(res.empty()) {
    return ;
  }
  if(fabs(res.back().getX() - res.front().getX()) > FLOAT_EPS || fabs(res.back().getY() - res.front().getY()) > FLOAT_EPS) {
    res.push_back(res.front());
  }
}

double area(const vector<Point> & pts)
{
  if(pts.empty()) {
    return 0.0;
  }
  double result = 0.0;
  for(unsigned int i = 0; i< pts.size()-1; ++i) {
    result += (pts[i].getX() * pts[i+1].getY() - pts[i].getY() * pts[i+1].getX());
  }
  return fabs(result)/2.0;
}

double intersectArea(const vector<Point>& polys1, const vector<Point>& polys2)
{
    vector<Point> pts1 = polys1;
    vector<Point> pts2 = polys2;
    pts1.push_back(pts1[0]);
    pts2.push_back(pts2[0]);
    vector<Point> res;
    for(unsigned int i = 0; i < polys2.size(); ++i) {
        res.clear();
        cutPolygon(pts2[i + 1], pts2[i], pts1, res);
        pts1 = res;
    }
    return area(res);
}

int main()
{
  int t;
  scanf("%d", &t);
  while(t--) {
    int n, m;
    scanf("%d %d", &n, &m);
    vector<Point> p, q;
    for(int i = 0; i < n; i++) {
      int a, b;
      scanf("%d %d", &a, &b);
      p.push_back(Point(a, b));
    }
    for(int i = 0; i < m; i++) {
      int a, b;
      scanf("%d %d", &a, &b);
      q.push_back(Point(a, b));
    }

    printf("%.4f\n", intersectArea(p, q));
  }
  return 0;
}