Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

半平面交~通俗易懂

Posted by ecjtu_yuweiwei at 2014-07-26 16:15:19 on Problem 1474
/*
参考博客:http://blog.csdn.net/accry/article/details/6070621
此博客对半平面方面知识讲得很全面,通俗

题意:就是一个在一个房子里面放一个摄像头
能将所有的地方监视到的放摄像头的地点的集合即为多边形的核
经常会遇到让你判定一个多边形是否有核的问题

此题利用半平面交求多边形的核
多边形的核:
它是平面简单多边形的核是该多边形内部的一个点集
该点集中任意一点与多边形边界上一点的连线都处于这个多边形内部。
*/
#include<iostream>
#include<queue>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<map>
#include<cstdlib>
#include<cmath>
const double eps=1e-8;
const double PI=acos(-1.0);
const double e=2.7182818284590452354;
const int INF=0x7fffffff;
const int Max=1001;
#define zero(x) (((x)>0?(x):-(x))<eps)
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int sign(double x)
{
    return (x>eps)-(x<-eps);
}
typedef struct Node
{
    double x;
    double y;
}point;
point list[Max],stack[Max];
point pp[Max],qq[Max],pnt[Max];
int n;
int top;

int cnt;
int curcnt;
double xmult(point p0,point p1,point p2)
{
	return(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
double Distance(point p1,point p2)// 返回两点之间欧氏距离
{
	return( sqrt( (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y) ) );
}
bool cmp(point p1,point p2)
{
    double temp;
    temp=xmult(list[0],p1,p2);
    if(temp>0)
        return true;
    if(temp==0&&(Distance(list[0],p1)<Distance(list[0],p2)))
        return true;
    return false;
}
void convex_hull()//凸包模板
{
    int i;
    for(i=1;i<n;i++)
    {
        point temp;
        if((list[i].y<list[0].y)||(list[i].y==list[0].y&&list[i].x<list[0].x))
            swap(list[0],list[i]);
    }
    sort(list+1,list+n,cmp);
    top=1;
    stack[0]=list[0];
    stack[1]=list[1];
    for(i=2;i<n;i++)
    {
        while(top>=1&&xmult(stack[top-1],stack[top],list[i])<=0)
            top--;
        top++;
        stack[top]=list[i];
    }
}
void Init(int n)//初始化
{
    int i;
    for(i=1;i<=n;i++)
    {
        pp[i]=pnt[i];
    }
    pp[n+1]=pp[1];//n个点有n条边
    pp[0]=pp[n];//用于计算相交的点(第n个点在直线左侧并且第一个点在右侧)
    cnt=n;//多边形顶点数
}
void GetLine(point u,point v,double &a,double &b,double &c)//两点确定一条直线
{
    a=v.y-u.y;
    b=u.x-v.x;
    c=v.x*u.y-u.x*v.y;
}
point Intersect(point u,point v,double a,double b,double c)//求直线切割交于多边形边上的一点
{
    double q=fabs(a*u.x+b*u.y+c);
    double p=fabs(a*v.x+b*v.y+c);
    point res;
    res.x=(p*u.x+q*v.x)/(q+p);
    res.y=(p*u.y+q*v.y)/(q+p);
    return res;
}
void CutLine(double a,double b,double c)//直线切割模板
{
    int i;
    curcnt=0;
    for(i=1;i<=cnt;i++)
    {
        if(a*pp[i].x+b*pp[i].y+c>=0)//当前顶点在直线的右侧(或者直线上)
        {
            qq[++curcnt]=pp[i];
        }
        else
        {
            if(a*pp[i-1].x+b*pp[i-1].y+c>0)//前一个顶点在直线的右侧
            {
                qq[++curcnt]=Intersect(pp[i],pp[i-1],a,b,c);
            }
            if(a*pp[i+1].x+b*pp[i+1].y+c>0)//同样的,后一个顶点在直线的右侧
            {
                qq[++curcnt]=Intersect(pp[i],pp[i+1],a,b,c);
            }
        }
    }
    for(i=1;i<=curcnt;i++)//更新切割后的多边形
    {
        pp[i]=qq[i];
    }
    pp[curcnt+1]=pp[1];
    pp[0]=pp[curcnt];
    cnt=curcnt;
}
int main()
{
    int m,i,j;
    double a,b,c,num;
    num=1;
    while(cin>>n&&n)
    {
        for(i=1;i<=n;i++)
        {
            cin>>pnt[i].x>>pnt[i].y;
        }
        pnt[n+1]=pnt[1];
        Init(n);
        //顺时针方向为切割后多边形
        for(i=1;i<=n;i++)
        {
            GetLine(pnt[i],pnt[i+1],a,b,c);
            CutLine(a,b,c);
        }
        cout<<"Floor #"<<num++<<endl;
        if(cnt==0)
            cout<<"Surveillance is impossible."<<endl;
        else
            cout<<"Surveillance is possible."<<endl;
        cout<<endl;//坑爹的没注意题目PE了一次
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator