正文

Gym 100952J&&2015 HIAST Collegiate Programming Contest J. Polygons Intersection【计算几何求解两个凸多边形的相交面积板子题】

IP云
IP云V管理员/8 阅读
06/20
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

J. Polygons Intersection

time limit per test：2 seconds
memory limit per test：64 megabytes
input：standard input
output：standard output

We will not waste your time, it is a straightforward problem. Given multiple polygons, calculate the area of their intersection. For simplicity, there will be exactly 2 polygons both of them are convex, given in the counterclockwise order and have non-zero areas. Furthermore, in one polygon a vertex won't be on the sides of the other one. The figure below demonstrates the first test case.

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

题目链接：http://codeforces.com/gym/100952/problem/J

题意：给2个凸多边形，求相交面积

思路：板子题，学习一下！

下面给出AC代码：

#include "iostream"
#include "string.h"
#include "stack"
#include "queue"
#include "string"
#include "vector"
#include "set"
#include "map"
#include "algorithm"
#include "stdio.h"
#include "math.h"
#define ll long long
#define bug(x) cout<<x<<" "<<"UUUUU"<<endl;
#define mem(a) memset(a,0,sizeof(a))
#define mp(x,y) make_pair(x,y)
using namespace std;
const long long INF = 1e18+1LL;
const int inf = 1e9+1e8;
const int N=1e5+;
#define maxn 510
const double eps=1E-;
int sig(double d){
return(d>eps)-(d<-eps);
}
struct Point{
double x,y; Point(){}
Point(double x,double y):x(x),y(y){}
bool operator==(const Point&p)const{
return sig(x-p.x)==&&sig(y-p.y)==;
}
};
double cross(Point o,Point a,Point b){
return(a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y);
}
double area(Point* ps,int n){
ps[n]=ps[];
double res=;
for(int i=;i<n;i++){
res+=ps[i].x*ps[i+].y-ps[i].y*ps[i+].x;
}
return res/2.0;
}
int lineCross(Point a,Point b,Point c,Point d,Point&p){
double s1,s2;
s1=cross(a,b,c);
s2=cross(a,b,d);
if(sig(s1)==&&sig(s2)==) return ;
if(sig(s2-s1)==) return ;
p.x=(c.x*s2-d.x*s1)/(s2-s1);
p.y=(c.y*s2-d.y*s1)/(s2-s1);
return ;
}
//多边形切割
//用直线ab切割多边形p，切割后的在向量(a,b)的左侧，并原地保存切割结果
//如果退化为一个点，也会返回去,此时n为1
void polygon_cut(Point*p,int&n,Point a,Point b){
static Point pp[maxn];
int m=;p[n]=p[];
for(int i=;i<n;i++){
if(sig(cross(a,b,p[i]))>) pp[m++]=p[i];
if(sig(cross(a,b,p[i]))!=sig(cross(a,b,p[i+])))
lineCross(a,b,p[i],p[i+],pp[m++]);
}
n=;
for(int i=;i<m;i++)
if(!i||!(pp[i]==pp[i-]))
p[n++]=pp[i];
while(n>&&p[n-]==p[])n--;
}
//---------------华丽的分隔线-----------------//
//返回三角形oab和三角形ocd的有向交面积,o是原点//
double intersectArea(Point a,Point b,Point c,Point d){
Point o(,);
int s1=sig(cross(o,a,b));
int s2=sig(cross(o,c,d));
if(s1==||s2==)return 0.0;//退化，面积为0
if(s1==-) swap(a,b);
if(s2==-) swap(c,d);
Point p[]={o,a,b};
int n=;
polygon_cut(p,n,o,c);
polygon_cut(p,n,c,d);
polygon_cut(p,n,d,o);
double res=fabs(area(p,n));
if(s1*s2==-) res=-res;return res;
}
//求两多边形的交面积
double intersectArea(Point*ps1,int n1,Point*ps2,int n2){
if(area(ps1,n1)<) reverse(ps1,ps1+n1);
if(area(ps2,n2)<) reverse(ps2,ps2+n2);
ps1[n1]=ps1[];
ps2[n2]=ps2[];
double res=;
for(int i=;i<n1;i++){
for(int j=;j<n2;j++){
res+=intersectArea(ps1[i],ps1[i+],ps2[j],ps2[j+]);
}
}
return res;//assumeresispositive!
}
//hdu-3060求两个任意简单多边形的并面积
Point ps1[maxn],ps2[maxn];
int n1,n2;
int main(){
int t;
cin>>t;
while(t--){
scanf("%d%d",&n1,&n2);
for(int i=;i<n1;i++)
scanf("%lf%lf",&ps1[i].x,&ps1[i].y);
for(int i=;i<n2;i++)
scanf("%lf%lf",&ps2[i].x,&ps2[i].y);
double ans=intersectArea(ps1,n1,ps2,n2);
//ans=fabs(area(ps1,n1))+fabs(area(ps2,n2))-ans;//容斥
printf("%.4f\n",ans);
}
return ;
}

Gym 100952J&&2015 HIAST Collegiate Programming Contest J. Polygons Intersection【计算几何求解两个凸多边形的相交面积板子题】的更多相关文章

  1. Gym 100952E&amp&semi;&amp&semi;2015 HIAST Collegiate Programming Contest E&period; Arrange Teams【DFS&plus;剪枝】

    E. Arrange Teams time limit per test:2 seconds memory limit per test:64 megabytes input:standard inp ...

  2. Gym 100952F&amp&semi;&amp&semi;2015 HIAST Collegiate Programming Contest F&period; Contestants Ranking【BFS&plus;STL乱搞&lpar;map&plus;vector&rpar;&plus;优先队列】

    F. Contestants Ranking time limit per test:1 second memory limit per test:24 megabytes input:standar ...

  3. Gym 100952A&amp&semi;&amp&semi;2015 HIAST Collegiate Programming Contest A&period; Who is the winner&quest;【字符串，暴力】

    A. Who is the winner? time limit per test:1 second memory limit per test:64 megabytes input:standard ...

  4. Gym 100952I&amp&semi;&amp&semi;2015 HIAST Collegiate Programming Contest I&period; Mancala【模拟】

    I. Mancala time limit per test:3 seconds memory limit per test:256 megabytes input:standard input ou ...

  5. Gym 100952H&amp&semi;&amp&semi;2015 HIAST Collegiate Programming Contest H&period; Special Palindrome【dp预处理&plus;矩阵快速幂&sol;打表解法】

    H. Special Palindrome time limit per test:1 second memory limit per test:64 megabytes input:standard ...

  6. Gym 100952D&amp&semi;&amp&semi;2015 HIAST Collegiate Programming Contest D&period; Time to go back【杨辉三角预处理，组合数，dp】

    D. Time to go back time limit per test:1 second memory limit per test:256 megabytes input:standard i ...

  7. Gym 100952C&amp&semi;&amp&semi;2015 HIAST Collegiate Programming Contest C&period; Palindrome Again &excl;&excl;【字符串，模拟】

    C. Palindrome Again !! time limit per test:1 second memory limit per test:64 megabytes input:standar ...

  8. Gym 100952G&amp&semi;&amp&semi;2015 HIAST Collegiate Programming Contest G&period; The jar of divisors【简单博弈】

    G. The jar of divisors time limit per test:2 seconds memory limit per test:64 megabytes input:standa ...

  9. Gym 100952B&amp&semi;&amp&semi;2015 HIAST Collegiate Programming Contest B&period; New Job【模拟】

    B. New Job time limit per test:1 second memory limit per test:64 megabytes input:standard input outp ...

随机推荐

  1. spring 官方下载地址（Spring Framework 3&period;2&period;x&amp&semi;Spring Framework 4&period;0&period;x）

    spring官方网站改版后,建议都是通过 Maven和Gradle下载,对不使用Maven和Gradle开发项目的,下载就非常麻烦,下给出Spring Framework jar官方直接下载路径: h ...

  2. TCP的那些事儿（下）

    TCP的那些事儿(下) 这篇文章是下篇,所以如果你对TCP不熟悉的话,还请你先看看上篇<TCP的那些事儿(上)> 上篇中,我们介绍了TCP的协议头.状态机.数据重传中的东西.但是TCP要解 ...

  3. 苹果审核Metadata Rejected

    最近提交了 公司的一个 app,收到了appStore拒绝的信息及邮件 拒绝后的状态改为了:metadata rejected 邮件里面有这样一句话 意思大致就是: 你的app先被显示为 Metada ...

  4. EIGR的非等价均衡P

    DUAL算法(离散更新算法或扩散更新算法) 配置 1.首先配置R1的IP R1(config)#inter f0/0 R1(config-if)#ip address 200.1.1.1 255.25 ...

  5. video，source元素

    一,视频 <video src="../[再一次快乐结局]第15集.mp4" controls="controls" width="500&qu ...

  6. javascript&comma;css3加载动画

    html代码 <!DOCTYPE html> <html> <head> <meta charset="utf-8"> <me ...

  7. AIO5程序中审批跳转条件：超过某一个值必须总经理审批

    以实际需求为例看下系统中如何设置: 客户需求:采购订单中对总金额进行限制,超过20000的话必须要经过总经理审批含税金额<20000:采购部门某个员工发起→直接主管批→财务主管知会含税金额≥20 ...

  8. git push的用法

    git push <远程仓库名> <本地分支名>:<远程分支名>

  9. xpath简单实用

    一.xpath 基本语法 /html /html/head/title 绝对路径(一层层的查找) /html//title 相对于当前节点 //title/./../.. . 当前节点 ..父节点 . ...

  10. iOS上传本地代码到git

    1.顾名思义,首先你得注册一个github账户 这个我就不细说了. 2.然后你得创建一个 repository  步骤见下图 3.相当于创建成功 会跳到下图界面 4.一看就很清楚了 create a ...