poj 1279 Art Gallery
2893 ワード
【題目大意】:時計回りにn個の点を与えて、多角形の核の面積を求めます
【解題の考え方】:半面交模版テスト
【コード】:
【解題の考え方】:半面交模版テスト
【コード】:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#include <string>
#include <cctype>
#include <map>
#include <iomanip>
using namespace std;
#define eps 1e-8
#define pi acos(-1.0)
#define inf 1<<30
#define linf 1LL<<60
#define pb push_back
#define lc(x) (x << 1)
#define rc(x) (x << 1 | 1)
#define lowbit(x) (x & (-x))
#define ll long long
#define MAXN 2000
struct Point {
double x,y;
Point() {}
Point(double _x,double _y){
x=_x,y=_y;
}
};
/* ( )( 1 )*/
Point points[MAXN],p[MAXN],q[MAXN];
int n;
double r;
int cCnt,curCnt;
int sig(double k){
return (k<-eps)?-1:(k>eps);
}
inline void getline(Point x,Point y,double &a,double &b,double &c){
a=y.y-x.y;
b=x.x-y.x;
c=y.x*x.y-x.x*y.y;
}
inline void initial(){
for (int i=1; i<=n; ++i) p[i]=points[i];
p[n+1]=p[1];
p[0]=p[n];
cCnt=n;
}
inline Point intersect(Point x,Point y,double a,double b,double c){
double u=fabs(a*x.x+b*x.y+c);
double v=fabs(a*y.x+b*y.y+c);
return Point((x.x*v+y.x*u)/(u+v),(x.y*v+y.y*u)/(u+v));
}
inline void cut(double a,double b ,double c){
curCnt=0;
for (int i=1; i<=cCnt; ++i){
if (sig(a*p[i].x+b*p[i].y+c)>=0) q[++curCnt]=p[i];
else {
if (sig(a*p[i-1].x+b*p[i-1].y+c)>0){
q[++curCnt]=intersect(p[i],p[i-1],a,b,c);
}
if(sig(a*p[i+1].x+b*p[i+1].y+c)>0){
q[++curCnt]=intersect(p[i],p[i+1],a,b,c);
}
}
}
for (int i=1; i<=curCnt; ++i) p[i]=q[i];
p[curCnt+1]=p[1];
p[0]=p[curCnt];
cCnt=curCnt;
return ;
}
inline void solve(){
// : , ,
initial();
for(int i=1; i<=n; ++i){
double a,b,c;
getline(points[i],points[i+1],a,b,c);
cut(a,b,c);
}
//
double area=0;
for (int i=1; i<=curCnt; ++i)
area+=p[i].x*p[i+1].y-p[i+1].x*p[i].y;
area=fabs(area/2.0);
printf("%.2f
",area);
// cCnt ,p
}
inline void GuiZhengHua(){
// , ,
for(int i = 1; i < (n+1)/2; i ++)
swap(points[i], points[n-i]);// iostream
}
int main() {
int T;
cin >> T;
while (T--){
scanf("%d",&n);
double a,b;
for (int i=1; i<=n; i++){
scanf("%lf%lf",&a,&b);
points[i]=Point(a,b);
}
points[n+1]=points[1];
// GuiZhengHua();
solve();
}
return 0;
}