http://poj.org/problem?id=1279

顺时针给你一个多边形...求能看到所有点的面积...用半平面对所有边取交即可,模版题

这里的半平面交是O(n^2)的算法...比较逗比...暴力对每条线段做半平面交...要注意的地方写在注释里了...顺序写反了卡了我好久

/********************* Template ************************/
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std; #define EPS 1e-8
#define MAXN 10005
#define MOD (int)1e9+7
#define PI acos(-1.0)
#define INF ((1LL)<<50)
#define max(a,b) ((a) > (b) ? (a) : (b))
#define min(a,b) ((a) < (b) ? (a) : (b))
#define max3(a,b,c) (max(max(a,b),c))
#define min3(a,b,c) (min(min(a,b),c))
#define BUG cout<<"BUG! "<<endl
#define LLINE cout<<"------------------"<<endl
#define L(t) (t << 1)
#define R(t) (t << 1 | 1)
#define Mid(a,b) ((a + b) >> 1)
#define lowbit(a) (a & -a)
#define FIN freopen("in.txt","r",stdin)
#pragma comment (linker,"/STACK:102400000,102400000") // typedef long long LL;
// typedef unsigned long long ULL;
// typedef __int64 LL;
// typedef unisigned __int64 ULL;
// int gcd(int a,int b){ return b?gcd(b,a%b):a; }
// int lcm(int a,int b){ return a*b/gcd(a,b); } /********************* F ************************/
struct POINT{
double x,y;
POINT(double _x = , double _y = ):x(_x),y(_y){}
}p[MAXN],q[MAXN],t[MAXN];
int n;
struct LINE{
double a,b,c;
POINT A,B;
LINE(POINT _a, POINT _b):A(_a),B(_b){
a=B.y-A.y;
b=A.x-B.x;
c=B.x*A.y-A.x*B.y;
}
};
double multiply(POINT sp,POINT ep,POINT op){ //叉积 左+ 右-
return (sp.x-op.x) * (ep.y-op.y) - (ep.x-op.x) * (sp.y-op.y);
}
POINT Intersection(LINE a,LINE b){ //直线交点
double u = fabs(b.A.x * a.a + b.A.y * a.b + a.c);
double v = fabs(b.B.x * a.a + b.B.y * a.b + a.c);
POINT t;
t.x = (b.A.x * v + b.B.x * u) / (u + v);
t.y = (b.A.y * v + b.B.y * u) / (u + v);
return t;
}
double Triangle_area(POINT a,POINT b,POINT c){ //求三角形面积(带符号)
return multiply(a,b,c)/;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("outm.txt","w",stdout);
int ct = ;
int T;
cin>>T;
while(T--){
cin>>n;
for(int i = ; i < n ; i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
//暴力对每一个向量作半平面交 ...即将右侧的点和与其他直线的交点加入集合
for(int i = ; i < n ; i++) q[i] = p[i];
int cnt = n;
for(int i = ; i < n ; i++){
int c = ;
for(int j = ; j < cnt ; j++){
//点在右侧
if(multiply(p[i],p[(i+)%n],q[j]) <= EPS) {
t[c++] = q[j];
}else { //点在左侧,但是前后线段和该直线有交点
//这个顺序不要写反,否则不是顺时针会WA
if(multiply(p[i],p[(i+)%n],q[(j-+cnt)%cnt]) < -EPS){
t[c++] = Intersection(LINE(p[i],p[(i+)%n]) , LINE(q[j],q[(j-+cnt)%cnt]));
}
if(multiply(p[i],p[(i+)%n],q[(j+)%cnt]) < -EPS){
t[c++] = Intersection(LINE(p[i],p[(i+)%n]) , LINE(q[j],q[(j+)%cnt]));
}
}
}
for(int j = ; j < c ; j++) q[j] = t[j];
cnt = c;
}
double area = ;
for(int i = ; i < cnt ; i++){
area += Triangle_area(POINT(,),q[i],q[(i+)%cnt]);
}
area = fabs(area);
printf("%.2lf\n",area);
}
return ;
}

最新文章

  1. CentOS升级openssl
  2. javascript数组去重的4个方法
  3. Enlisting multiple 1-phase aware participants in the same transaction
  4. [问题2014A01] 复旦高等代数 I(14级)每周一题(第三教学周)
  5. Linux下SSH的Log文件路径
  6. cas sso单点登录系列7_ 单点登录cas常见问题系列汇总
  7. OpenRTSP的使用
  8. 配置主机路由表(route)(两)
  9. kubernetes 命令使用
  10. 什么是DOM,DOM level 1\2\3 的区别是什么
  11. 【Docker笔记】-开启TCP管理端口
  12. spring-security权限管理学习目标
  13. Catch a Memory Access Violation in C++
  14. 安装使用hibernate tools
  15. Ruby数组的操作
  16. [Beego模型] 一、ORM 使用方法
  17. 每天CSS学习之!important
  18. ASP.NET之通过JS向服务端(后台)发出请求(__doPostBack is undefined)
  19. Android指南 - 样式和主题
  20. hdu 5310(贪心)

热门文章

  1. HDU 1789 Doing Homework again【贪心】
  2. Kubernetes本地私有仓库配置
  3. 同门不同类—创新Aurvana Live2/Air简评(附随身视听设备心路历程)
  4. PHP -Casbin: 支持 ACL、RBAC、ABAC 多种模型的 PHP 权限管理框架
  5. 今日SGU 5.29
  6. unity 天空盒有缝隙的解决方案
  7. 【转】C# HttpWebRequest提交数据方式
  8. hdu 4324 Triangle LOVE(拓扑判环)
  9. BZOJ 2982 combination Lucas定理
  10. hdu(1069)——Monkey and Banana(LIS变形)