poj2540Hotter Colder(半平面交)

链接

根据距离可以列得直线方程,附上初始矩形的四个顶点,依次用直线切割。

 #include<iostream>
#include <stdio.h>
#include <math.h>
#include<cstring>
#include<algorithm>
#define eps 1e-8
using namespace std;
const int MAXN=;
int m;
double r,tx,ty,ans;
int cCnt,curCnt;//此时cCnt为最终切割得到的多边形的顶点数、暂存顶点个数
struct point
{
double x,y;
point(double x=,double y=):x(x),y(y) {}
};
point points[MAXN],p[MAXN],q[MAXN];//读入的多边形的顶点(顺时针)、p为存放最终切割得到的多边形顶点的数组、暂存核的顶点
void getline(point x,point y,double &a,double &b,double &c) //两点x、y确定一条直线a、b、c为其系数
{
a = y.y - x.y;
b = x.x - y.x;
c = y.x * x.y - x.x * y.y;
}
void initial()
{
for(int i = ; i <= m; ++i)p[i] = points[i];
p[m+] = p[];
p[] = p[m];
cCnt = m;//cCnt为最终切割得到的多边形的顶点数,将其初始化为多边形的顶点的个数
}
point intersect(point x,point y,double a,double b,double c) //求x、y形成的直线与已知直线a、b、c、的交点
{
//cout<<a<<" "<<b<<" "<<c<<endl;
double u = fabs(a * x.x + b * x.y + c);
double v = fabs(a * y.x + b * y.y + c);
// cout<<u<<" "<<v<<endl;
point pt;
pt.x=(x.x * v + y.x * u) / (u + v);
pt.y=(x.y * v + y.y * u) / (u + v);//cout<<pt.x<<" -"<<pt.y<<" "<<x.x<<" "<<y.x<<endl;
return pt;
}
void cut(double a,double b ,double c)
{
curCnt = ;
for(int i = ; i <= cCnt; ++i)
{
if(a*p[i].x + b*p[i].y + c > -eps)q[++curCnt] = p[i];
else
{
if(a*p[i-].x + b*p[i-].y + c > eps)
{
q[++curCnt] = intersect(p[i-],p[i],a,b,c);
}
if(a*p[i+].x + b*p[i+].y + c > eps) //原理同上
{
q[++curCnt] = intersect(p[i],p[i+],a,b,c);
}
}
//cout<<q[curCnt].x<<" --"<<q[curCnt].y<<" "<<i<<" "<<p[i].x<<" "<<p[i].y<<endl;
}
for(int i = ; i <= curCnt; ++i)p[i] = q[i];
p[curCnt+] = q[];
p[] = p[curCnt];
cCnt = curCnt;
}
int dcmp(double x)
{
if(fabs(x)<eps) return ;
return x<?-:;
}
void solve(double x,double y,int flag)
{
double a,b,c;
if(flag == )
{
a = -*x+*tx,b = -*y+*ty,c = x*x+y*y-tx*tx-ty*ty;
}
else if(flag==)
{
a = *x-*tx,b = *y-*ty,c = tx*tx+ty*ty-x*x-y*y;
}
// if(dcmp(a)==0&&dcmp(b)==0&&dcmp(c)<=0)
// {
// ans = 0;
// return ;
// }
cut(a,b,c);
}
int main()
{
points[] = point(,);
points[] = point(,);
points[] = point(,);
points[] = point(,);
p[] = p[];
m = ;
tx = ,ty=;
char s[];
double x,y;
initial();
while(scanf("%lf%lf%s",&x,&y,s)!=EOF)
{
int flag;
if(strcmp(s,"Colder")==||strcmp(s,"Same")==)solve(x,y,);
if(strcmp(s,"Hotter")==||strcmp(s,"Same")==)solve(x,y,);
tx = x,ty=y;
double area = ;
for(int i = ; i <= cCnt; ++i)
{
//cout<<p[i].x<<" "<<p[i].y<<endl;
area += p[i].x * p[i + ].y - p[i + ].x * p[i].y;
}
area = fabs(area / 2.0);
ans = area;
printf("%.2f\n",ans);
}
}
上一篇:强大的游戏开发工具Unity3D推出2D开发工具,unity将混合3D与2D开发


下一篇:Python开发【第十六篇】:AJAX全套