兩個凸多邊形的交
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
struct point
{
double x,y;
};
vector <point> polygon, scissor, temp;
double operator *(point p1, point p2)
{
return p1.x * p2.y - p1.y * p2.x;
}
point operator +(point p1, point p2)
{
point p;
p.x = p1.x + p2.x;
p.y = p1.y + p2.y;
return p;
}
point operator -(point p1, point p2)
{
point p;
p.x = p1.x - p2.x;
p.y = p1.y - p2.y;
return p;
}
bool at_right(point p1, point p2, point p)
{
return (p - p1) * (p2 - p1) <= 0;
}
bool intersect(point p1, point p2, point p3, point p4, point &p)
{
if ( ((p3 - p1) * (p2 - p1)) * ((p4 - p1) * (p2 - p1)) >= 0 )
return 0;
double D, D1, D2;
D = (p1 - p2) * (p4 - p3);
D1 = (p3 * p4) * (p1.x - p2.x) - (p1 * p2) * (p3.x - p4.x);
D2 = (p1 * p2) * (p4.y - p3.y) - (p3 * p4) * (p2.y - p1.y);
p.x = D1 / D;
p.y = D2 / D;
return 1;
}
double getarea(point p1, point p2, point p3)
{
return fabs((p1 - p2) * (p3 - p2)) / 2.0;
}
int main()
{
int scin, poln, i, j;
double area = 0.0;
point pp;
scanf("%d", &poln);
for (i = 0; i < poln; ++i)
{
scanf("%lf%lf", &pp.x, &pp.y);
polygon.push_back(pp);
}
scanf("%d",&scin);
for (i = 0; i < scin; ++i)
{
scanf("%lf%lf", &pp.x, &pp.y);
scissor.push_back(pp);
}
scissor.push_back(scissor[0]);
for (i = 0; i < scin; ++i)
{
temp.clear();
if (polygon.size() < 3)
break;
for (j = 0; j < polygon.size() - 1; ++j)
{
if (intersect(scissor[i], scissor[i + 1], polygon[j], polygon[j + 1], pp))
temp.push_back(pp);
if (at_right(scissor[i], scissor[i + 1], polygon[j + 1]))
temp.push_back(polygon[j + 1]);
}
if (intersect(scissor[i], scissor[i + 1], polygon[j], polygon[0], pp))
temp.push_back(pp);
if (at_right(scissor[i], scissor[i + 1], polygon[0]))
temp.push_back(polygon[0]);
polygon = temp;
}
if (polygon.size() > 2)
for (i = 1; i < polygon.size() - 1; ++i)
area += getarea(polygon[0], polygon[i], polygon[i + 1]);
printf("%.2lf\n",area);
return 0;
}