精华内容
下载资源
问答
  • 多边形的核

    2013-11-16 21:46:10
    //读入的多边形的顶点(顺时针)、p为存放最终切割得到的多边形顶点的数组、暂存的顶点 int cCnt, n; //此时cCnt为最终切割得到的多边形的顶点数、暂存顶点个数 inline int dbcmp(double x) { //精度问题 if(x...
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    
    #define CL(arr, val)    memset(arr, val, sizeof(arr))
    #define REP(i, n)       for((i) = 0; (i) < (n); ++(i))
    #define FOR(i, l, h)    for((i) = (l); (i) <= (h); ++(i))
    #define FORD(i, h, l)   for((i) = (h); (i) >= (l); --(i))
    #define L(x)    (x) << 1
    #define R(x)    (x) << 1 | 1
    #define MID(l, r)   (l + r) >> 1
    #define Min(x, y)   x < y ? x : y
    #define Max(x, y)   x < y ? y : x
    #define E(x)    (1 << (x))
    
    const double eps = 1e-8;
    typedef long long LL;
    using namespace std;
    
    const int maxn = 110;
    
    struct Point {
        double x;
        double y;
        Point(double a = 0, double b = 0): x(a), y(b) {}
        void input() {
            scanf("%lf%lf", &x, &y);
        }
    };
    
    Point point[maxn], p[maxn], q[maxn];    //读入的多边形的顶点(顺时针)、p为存放最终切割得到的多边形顶点的数组、暂存核的顶点  
    int cCnt, n;    //此时cCnt为最终切割得到的多边形的顶点数、暂存顶点个数
    
    inline int dbcmp(double x) {    //精度问题
        if(x > eps) return 1;
        else if(x < -eps)   return -1;
        return 0;
    }
    
    inline void getline(Point x, Point y, double& a, double& b, double& c) {    //点X,Y确定一条直线
        a = y.y - x.y;
        b = x.x - y.x;
        c = y.x*x.y - x.x*y.y;
    }
    
    inline Point intersect(Point x, Point y, double a, double b, double c) {    求x、y形成的直线与已知直线a、b、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) {        //如上图所示,切割
        int cur = 0, i;
        for(i = 1; i <= cCnt; ++i) {
            if(dbcmp(a*p[i].x + b*p[i].y + c) >= 0)  q[++cur] = p[i];    // c由于精度问题,可能会偏小,所以有些点本应在右侧而没在
            else {
                if(dbcmp(a*p[i-1].x + b*p[i-1].y + c) > 0)    //如果p[i-1]在直线的右侧的话,  
                    //则将p[i],p[i-1]形成的直线与已知直线的交点作为核的一个顶点(这样的话,由于精度的问题,核的面积可能会有所减少)  
                    q[++cur] = intersect(p[i], p[i-1], a, b, c);
                if(dbcmp(a*p[i+1].x + b*p[i+1].y + c) > 0)
                    q[++cur] = intersect(p[i], p[i+1], a, b, c);
            }
        }
        for(i = 1; i <= cur; ++i)   p[i] = q[i];
        p[cur+1] = q[1]; p[0] = p[cur];
        cCnt = cur;
    }
    
    void solve() {    //注意:默认点是顺时针,如果题目不是顺时针,规整化方向 
        int i;
        for(i = 1; i <= n; ++i) {
            double a, b, c;
            getline(point[i], point[i+1], a, b, c);
            cut(a, b, c);
        }
        if(cCnt == 0)   puts("NO");
        else    puts("YES");
    }
    
    void init() {
        int i;
        FOR(i, 1, n)    point[i].input();
        point[n+1] = point[1];
        //初始化p[], cCnt
        FOR(i, 1, n)    p[i] = point[i];
        p[n+1] = p[1]; p[0] = p[n];
        cCnt = n;
    }
    
    int main() {
        //freopen("data.in", "r", stdin);
        int t;
        scanf("%d", &t);
        while(t--) {
            scanf("%d", &n);
            init();
            solve();
        }
        return 0;
    }
    
    *************************************************************************************
    HDU1474
    #include 
    #include 
    #include 
    using namespace std; 
    struct Point 
    { 
        double x, y; 
    } point[105]; //原始节点 
     
    Point p[105];//保存新切割出的多边形 
    Point q[105];//临时保存新切割的多边形 
    int n, m; 
    double a, b, c;//直线 ax + by + c == 0 
    void lineFromSegment(Point p1, Point p2) 
    { 
        //线段所在直线,返回直线方程的三个系数 
        a = p2.y - p1.y; 
        b = p1.x - p2.x; 
        c = p2.x * p1.y - p1.x * p2.y; 
    } 
    Point intersect(Point x, Point y) 
    { 
        double u = fabs(a * x.x + b * x.y + c); 
        double v = fabs(a * y.x + b * y.y + c); 
        Point ans; 
        ans.x = (x.x * v + y.x * u) / (u + v); 
        ans.y = (x.y * v + y.y * u) / (u + v); 
        return ans; 
    }//获取直线ax+by+c==0  和点x和y所连直线的交点 
    int cut() 
    { 
        int np = 0, i; 
        for( i = 0 ; i < m ; i++) 
        { 
            if( p[i].x *a + p[i].y *b + c >= 0)  //题目输入是顺时针方向故大于号 
            { 
                q[np++] = p[i]; 
            }//某点在该直线割后的多边形内,则保存该点 
            else 
            { 
                if( p[(i + m - 1) % m].x * a + p[(i + m - 1) % m].y * b + c > 0 )// 
                { 
                    q[np++] = intersect(p[i], p[(i + m - 1) % m]); 
                } 
     
                if( p[(i + 1) % m].x * a + p[(i + 1) % m].y * b + c > 0 ) 
                { 
                    q[np++] = intersect(p[i], p[(i + 1) % m]); 
                } 
            }//如果该点在外,看是该点的相邻两边是否存在与割线的交点,有交点保存割边上的交点 
        } 
        for( i = 0 ; i < np ; i++) 
            p[i] = q[i];//更新切割后的多边形顶点 
        m = np; 
        return 0; 
    } 
    int find_nucleus() 
    { 
        int i, j; 
        for( i = 0; i < n; i++) 
            p[i] = point[i]; 
        m = n; 
        for( i = 0 ; i < n ; i++) 
        { 
            lineFromSegment(point[i], point[(i + 1) % n]); 
            cut(); 
        } 
        return 0; 
    } 
    int main() 
    { 
        int i, k; 
        k = 1; 
        while(scanf("%d", &n), n) 
        { 
            for( i = 0 ; i < n ; i++) 
                scanf("%lf%lf", &point[i].x, &point[i].y); 
            find_nucleus(); 
            printf("Floor #%d\n", k++); 
            printf("%s\n\n", m == 0 ? "Surveillance is impossible." : "Surveillance is possible."); 
        } 
        return 0; 
    } 

    展开全文
  • 多边形核: 多边形的核相当于在某一点能看到所有顶点(不穿过边),这些点的集合就是多边形的核。 题目:POJ - 1279 细节:判断点是不是顺时针输入的,可以判断多边形面积,如果面积为负,则输入顺序是顺时针,需要...

    多边形核: 多边形的核相当于在某一点能看到所有顶点(不穿过边),这些点的集合就是多边形的核。

    题目:POJ - 1279

    细节:判断点是不是顺时针输入的,可以判断多边形面积,如果面积为负,则输入顺序是顺时针,需要改成逆时针(多数算法都是以逆时针顺序为基础)

    #include<bits/stdc++.h>
    #define ll long long
    #define lf double
    #define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    #define DEBUG cout<<",here\n";
    #define Rep(i,l,r) for(int i=(l);i<=(r);i++)
    using namespace std;
    
    struct Point{double x,y;};
    typedef Point vector_t;
    typedef Point point_t;
    struct Line{Point x;vector_t v;};
    
    double Cross(const vector_t& x, const vector_t& y){return x.x * y.y - x.y * y.x;}
    
    vector_t operator*(const vector_t& v,double t){return (vector_t){v.x*t,v.y*t};}
    vector_t operator+(const vector_t& a,const vector_t&b){return (vector_t){a.x+b.x,a.y+b.y};}
    Point operator-(const Point&a,const Point&b){return (Point){a.x-b.x,a.y-b.y};}
    //调用前需保证 Cross(v, w) != 0
    point_t GetLineIntersection(Line a,Line b){//求两直线交点
        Point P=a.x;vector_t v=a.v;
        Point Q=b.x;vector_t w=b.v;
        vector_t u = P-Q;
        double t = Cross(w, u)/Cross(v, w);
        return P+v*t;//由直线的点向式而来
    }
    
    double eps=1e-8;
    Point tmpP[2500];
    Line tmpL[2500];
    bool cmp1(const Line& a,const Line& b) { return atan2(a.v.y,a.v.x)<atan2(b.v.y,b.v.x); }//极角排序
    bool Onleft(Line l,Point p) { return Cross(l.v,(p-l.x)) > 0; }//ToLeftTest
    int dcmp(double x){ if(fabs(x)<eps)return 0; if(x>0)return 1; return -1;}
    int HalfPol(Line *l,int n,vector<Point> &p)
    {
        sort(l,l+n,cmp1);//把边按极角排序
        int hd = 0,tl = 0;
        tmpL[0] = l[0];
        for(int i=0;i<n;i++)
        {
            while(hd<tl&&!Onleft(l[i],tmpP[tl-1]))tl--;
            while(hd<tl&&!Onleft(l[i],tmpP[hd]))hd++;
            tmpL[++tl] = l[i];
            if(!dcmp(Cross(tmpL[tl].v,tmpL[tl-1].v)))
            {
                tl--;
                if(Onleft(tmpL[tl],l[i].x))tmpL[tl]=l[i];
            }
            if(hd<tl)tmpP[tl-1] = GetLineIntersection(tmpL[tl-1],tmpL[tl]);
        }
        while(hd<tl&&!Onleft(tmpL[hd],tmpP[tl-1]))tl--;
        if(tl-hd<=1)return 0;
        tmpP[tl] = GetLineIntersection(tmpL[hd],tmpL[tl]);
        for(int i=hd;i<=tl;i++)p.push_back(tmpP[i]);
        return tl-hd+1;
    }
    double PolygonArea(point_t* p, int n){//p为端点集合,n为端点个数
        double s = 0;
        for(int i = 1; i < n-1; i++)
            s += Cross(p[i]-p[0], p[i+1]-p[0]);
        return s/2;
    }
    
    int n,m;
    Point P[2505];
    Line L[2505];
    vector<Point>s;
    Point ss[2505];
    
    int main()
    {
    	int t;
    	cin>>t;
    	while(t--)
    	{
    		cin>>n;
    		s.clear();
    		int cntl=0;
    		Rep(i,0,n-1){
    			double x,y;cin>>x>>y;
    			P[i].x=x;P[i].y=y;
    		}
    		if(PolygonArea(P,n)<eps){//判断输入是否为顺时针
    			for(int i=0;i<n/2;i++){
    				swap(P[i],P[n-i-1]);
    			}
    		}
    		for(int i=0;i<n;i++){
    			L[cntl].v=P[(i+1)%n]-P[i];
    			L[cntl].x=P[i];
    			cntl++;
    		}
    		int sn=HalfPol(L,cntl,s);
    		for(int i=0;i<sn;i++){ss[i]=s[i];}
    		double S=PolygonArea(ss,sn);
    		printf("%.2f\n",S);
    	}
        return 0;
    }
    
    展开全文
  • 1.题目链接。...多边形的核是一个点集,在这个点集内部,可以看到边界上的任意一个点。求解方法采用半平面交。 #include<iostream> #include<cstdio> #include<stdio.h> #incl...

    1.题目链接。题目大意:给定一个多边形,是不是在这个多边形的内部存在一个点使得站在这个点可以看到多边形中的任意一个点。

    2.一个与多边形核有关的问题。多边形的核是一个点集,在这个点集内部,可以看到边界上的任意一个点。求解方法采用半平面交。

    #include<iostream>
    #include<cstdio>
    #include<stdio.h>
    #include<cstring>
    using namespace std;
    #pragma warning(disable:4996)
    struct node
    {
    	double x;
    	double y;
    } p[110], temp[110], newp[110];//p是最开始的多边形的每个点,temp是中间过程中临时存的多边形的每个点,newp是切割后的多边形的每个点
    int n, newn;//原来的点数,切割后的点数
    //直线方程的三个系数
    double a, b, c;
    void getline(node x, node y)//求x与y两点确定的直线方程ax+by+c=0
    {
    	a = y.y - x.y;
    	b = x.x - y.x;
    	c = y.x*x.y - y.y*x.x;
    }
    node intersect(node x, node y)//求x与y点确定的直线与ax+by+c=0这条直线的交点
    {
    	double u = a * x.x + b * x.y + c;
    	double v = a * y.x + b * y.y + c;
    	node t;
    	t.x = (x.x*v + y.x*u) / (u + v);//y.y-x.y=u+v;y.y-t.y=v;y.y-x.y=u;
    	t.y = (x.y*v + y.y*u) / (u + v);
    	return t;
    }
    void cut()
    {
    	int cutn = 0;
    	for (int i = 1; i <= newn; i++)
    	{
    		if (a*newp[i].x + b * newp[i].y + c >= 0)//所有的点都大于0,说明所有的点都在这条直线的另一边,所以不用切
    			temp[++cutn] = newp[i];
    		else
    		{
    			if (a*newp[i - 1].x + b * newp[i - 1].y + c > 0)
    				temp[++cutn] = intersect(newp[i - 1], newp[i]);//把新交点加入
    			if (a*newp[i + 1].x + b * newp[i + 1].y + c > 0)
    				temp[++cutn] = intersect(newp[i + 1], newp[i]);
    		}
    	}
    	for (int i = 1; i <= cutn; i++)
    		newp[i] = temp[i];
    	newp[cutn + 1] = temp[1];//能够找出所有点的前驱和后继
    	newp[0] = temp[cutn];
    	newn = cutn;
    }
    
    void solve()
    {
    	for (int i = 1; i <= n; i++)
    	{
    		newp[i] = p[i];
    	}
    	p[n + 1] = p[1];
    	newp[n + 1] = newp[1];
    	newp[0] = newp[n];
    	newn = n;
    	for (int i = 1; i <= n; i++)
    	{
    		getline(p[i], p[i + 1]);//从头开始顺序遍历两个相邻点。
    		cut();
    	}
    
    }
    int main()
    {
    	int T;
    	scanf("%d", &T);
    	while (T--)
    	{
    		scanf("%d", &n);
    		for (int i = 1; i <= n; i++)
    			scanf("%lf %lf", &p[i].x, &p[i].y);
    		solve();
    		if (newn == 0) puts("NO");
    		else
    			puts("YES");
    	}
    	return 0;
    }

     

    展开全文
  • 所谓多边形的核 是多边形中的一个点集 满足其中的点与多边形边上的点的连线全部在多边形中 用多边形的每一条边所在的直线去切整个坐标平面 得到的一个凸包就是核 #include<iostream> #include<...

    POJ1279 给一个多边形 求它的核的面积

    所谓多边形的核 是多边形中的一个点集 满足其中的点与多边形边上的点的连线全部在多边形中

     

    用多边形的每一条边所在的直线去切整个坐标平面 得到的一个凸包就是核

     

    #include<iostream>
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<math.h>
    #include<algorithm>
    #include<queue>
    #include<vector>
    using namespace std;
    
    const double eps=1e-9;
    
    int cmp(double x)
    {
     if(fabs(x)<eps)return 0;
     if(x>0)return 1;
     	else return -1;
    }
    
    const double pi=acos(-1.0);
    
    inline double sqr(double x)
    {
     return x*x;
    }
    
    
    
    
    
    
    struct point
    {
     double x,y;
     point (){}
     point (double a,double b):x(a),y(b){}
     void input()
     	{
     	 scanf("%lf%lf",&x,&y);
    	}
     friend point operator +(const point &a,const point &b)
     	{
     	 return point(a.x+b.x,a.y+b.y);
    	}	
     friend point operator -(const point &a,const point &b)
     	{
     	 return point(a.x-b.x,a.y-b.y);
    	}
     friend bool operator ==(const point &a,const point &b)
     	{
     	 return cmp(a.x-b.x)==0&&cmp(a.y-b.y)==0;
    	}
     friend point operator *(const point &a,const double &b)
     	{
     	 return point(a.x*b,a.y*b);
    	}
     friend point operator*(const double &a,const point &b)
     	{
     	 return point(a*b.x,a*b.y);
    	}
     friend point operator /(const point &a,const double &b)
     	{
     	 return point(a.x/b,a.y/b);
    	}
     double norm()
     	{
     	 return sqr(x)+sqr(y);
    	}
    };
    
    struct line
    {
     point a,b;
     line(){};
     line(point x,point y):a(x),b(y)
     {
     	
     }
    };
    double det(const point &a,const point &b)
    {
     return a.x*b.y-a.y*b.x;
    }
    
    double dot(const point &a,const point &b)
    {
     return a.x*b.x+a.y*b.y; 
    }
    
    double dist(const point &a,const point &b)
    {
     return (a-b).norm();
    }
    
    point rotate_point(const point &p,double A)
    {
     double tx=p.x,ty=p.y;
     return point(tx*cos(A)-ty*sin(A),tx*sin(A)+ty*cos(A));
    }
    
    
    
    
    bool parallel(line a,line b)
    {
     return !cmp(det(a.a-a.b,b.a-b.b));
    }
    
    bool line_joined(line a,line b,point &res)
    {
     if(parallel(a,b))return false;
     double s1=det(a.a-b.a,b.b-b.a);
     double s2=det(a.b-b.a,b.b-b.a);
     res=(s1*a.b-s2*a.a)/(s1-s2);
     return true;
    }
    
    bool pointonSegment(point p,point s,point t)
    {
     return cmp(det(p-s,t-s))==0&&cmp(dot(p-s,p-t))<=0;
    }
    
    void PointProjLine(const point p,const point s,const point t,point &cp)
    {
     double r=dot((t-s),(p-s))/dot(t-s,t-s);
     cp=s+r*(t-s);
    }
    
    
    
    
    struct polygon_convex
    {
     vector<point>P;
     polygon_convex(int Size=0)
     	{
     	 P.resize(Size);
    	}	
    };
    
    struct halfPlane
    {
     double a,b,c;
     halfPlane(point p,point q)
     	{
     	 a=p.y-q.y;
     	 b=q.x-p.x;
     	 c=det(p,q);
    	}
     halfPlane(double aa,double bb,double cc)
     	{
     	 a=aa;b=bb;c=cc;
    	}
     
     	
    };
    
    
    double calc(halfPlane &L,point &a)
    {
     return a.x*L.a +a.y*L.b+L.c;
    }
    
    point Intersect(point &a,point &b,halfPlane &L)
    {
     point res;
     double t1=calc(L,a),t2=calc(L,b);
     res.x=(t2*a.x-t1*b.x)/(t2-t1);
     res.y=(t2*a.y-t1*b.y)/(t2-t1);
     //cout<<res.x<<" "<<res.y<<endl;
     return res;
    }
    
    
    
    polygon_convex cut(polygon_convex &a,halfPlane &L)
    {
     int n=a.P.size();
     polygon_convex res;
     for(int i=0;i<n;i++)
     	{
     	 if(calc(L,a.P[i])<-eps)res.P.push_back(a.P[i]);
     	 	else	
     	 		{
     	 		 int j;
     	 		 j=i-1;
     	 		 if(j<0)j=n-1;
     	 		 if(calc(L,a.P[j])<-eps)
    			   	  res.P.push_back(Intersect(a.P[j],a.P[i],L));
     	 		 j=i+1;
     	 		 if(j==n)j=0;
     	 		 if(calc(L,a.P[j])<-eps)
     	 		 	res.P.push_back(Intersect(a.P[i],a.P[j],L));
    			}
    	}
     return res;
    }
    double INF=1e+5;
    polygon_convex core(vector<point> &a)
    {
     polygon_convex res;
     res.P.push_back(point(-INF,-INF));
     res.P.push_back(point(INF,-INF));
     res.P.push_back(point(INF,INF));
     res.P.push_back(point(-INF,INF));
     int n=a.size();
     for(int i=0;i<n;i++)
     	{
     	 halfPlane L(a[i],a[(i+1)%n]);
     	 res=cut(res,L);
    	}
     return res;
    }
    bool comp_less(const point &a,const point &b)
    {
     return cmp(a.x-b.x)<0||cmp(a.x-b.x)==0&&cmp(a.y-b.y)<0;
     
    }
    
    
    polygon_convex convex_hull(vector<point> a)
    {
     polygon_convex res(2*a.size()+5);
     sort(a.begin(),a.end(),comp_less);
     a.erase(unique(a.begin(),a.end()),a.end());//删去重复点 
     int m=0;
     for(int i=0;i<a.size();i++)
     	{
     	 while(m>1&&cmp(det(res.P[m-1]-res.P[m-2],a[i]-res.P[m-2]))<=0)--m;
     	 res.P[m++]=a[i];
    	}
     int k=m;
     for(int i=int(a.size())-2;i>=0;--i)
     	{
     	 while(m>k&&cmp(det(res.P[m-1]-res.P[m-2],a[i]-res.P[m-2]))<=0)--m;
     	 res.P[m++]=a[i];
    	}
     res.P.resize(m);
     if(a.size()>1)res.P.resize(m-1);
     return res;
    }
    
    bool is_convex(vector<point> &a)
    {
     for(int i=0;i<a.size();i++)
     	{
     	 int i1=(i+1)%int(a.size());
     	 int i2=(i+2)%int(a.size());
     	 int i3=(i+3)%int(a.size());
     	 if((cmp(det(a[i1]-a[i],a[i2]-a[i1]))*cmp(det(a[i2]-a[i1],a[i3]-a[i2])))<0)
    	  	return false;
    	}
     return true;
    }
    int containO(const polygon_convex &a,const point &b)
    {
     int n=a.P.size();
     point g=(a.P[0]+a.P[n/3]+a.P[2*n/3])/3.0;
     int l=0,r=n;
     while(l+1<r)
     	{
     	 int mid=(l+r)/2;
     	 if(cmp(det(a.P[l]-g,a.P[mid]-g))>0)
     	 	{
     	 	 if(cmp(det(a.P[l]-g,b-g))>=0&&cmp(det(a.P[mid]-g,b-g))<0)r=mid;
     	 	 	else l=mid;
    		}else
    			{
    			 if(cmp(det(a.P[l]-g,b-g))<0&&cmp(det(a.P[mid]-g,b-g))>=0)l=mid;
     	 	 		else r=mid;	
    			}
    	} 
     r%=n;
     int z=cmp(det(a.P[r]-b,a.P[l]-b))-1;
     if(z==-2)return 1;
     return z;	
    }
    long long int distant(point a,point b)
    {
     return  (int(b.x)-int(a.x))*(int(b.x)-int(a.x))+(int(b.y)-int(a.y))*(int(b.y)-int(a.y));
    }
    double  convex_diameter(polygon_convex &a,int &First,int &Second)
    {
     vector<point> &p=a.P;
     int n=p.size();
     double maxd=0;
     if(n==1)
     	{
     	 First=Second=0;
     	 return maxd;
    	}
     #define next(i)((i+1)%n)
     for(int i=0,j=1;i<n;++i)
     	{
     	 while(cmp(det(p[next(i)]-p[i],p[j]-p[i])-det(p[next(i)]-p[i],p[next(j)]-p[i]))<0)
     	 	j=next(j);
     	 double d=dist(p[i],p[j]);
     	 if(d>maxd)
     	 	{
     	 	 maxd=d;
     	 	 First=i,Second=j;
    		}
    	 d=dist(p[next(i)],p[next(j)]);
    	 if(d>maxd)
    	 	{
    	 	 maxd=d;
     	 	 First=next(i),Second=next(j);
    		}
    	 
    	}
     return maxd;
    }
    
    
    double area(vector<point>a)
    {
     double sum=0;
     for(int i=0;i<a.size();i++)
     	sum+=det(a[(i+1)%(a.size())],a[i]);
     	return sum/2.;
    }
    vector<point> pp;
    int main()
    {freopen("t.txt","r",stdin);
     int T;
     scanf("%d",&T);
     while(T--)
     	{
     	 int n;
     	 scanf("%d",&n);
     	 pp.resize(n);
     	 for(int i=0;i<n;i++)
     	 	pp[i].input();
     	 polygon_convex pc=core(pp);
     	 printf("%.2lf\n",-area(pc.P)+0.0005);
    	}
     return 0;
    }
    

      

     

    转载于:https://www.cnblogs.com/heisenberg-/p/6700949.html

    展开全文
  • <!-- @page { margin: 2cm } P { margin-bottom: 0.21cm } A:link { color: #0000ff } --> ... 这个问题是所谓多边形的核,在一个多边形(不一定是凸的),...
  • 多边形的核 模板

    2012-06-26 20:37:00
    直线切割多边形,公共的部分就是多边形的核 这里找到一个不错的模板:http://blog.csdn.net/accry/article/details/6070621 http://blog.csdn.net/candy20094369/article/details/6703940 #incl...
  • 还是计算几何, 多边形的核可以这样理解:这个核为原多边形内部的一个多边形,站在这个叫核的多边形中,我们能看到原多边形的任何一个位置。 算法步骤如下: 1.根据原多边形最大和最小的x,y初始化核多边形,就是个...
  • 简单多边形的每条边都分割平面,所有线都取其一半,交集就是简单多边形的核,也就是可以看到多边形所有区域的区域。 求解 original link - http://poj.org/problem?id=3335 references - ...
  • 关于多边形的核,我的这篇博客有介绍,就不多说了,差不多就是粘模板吧。 POJ1279求多边形核的面积(貌似G++编译器有问题,C++就过了)#include #include #include #define MAXN 1550 using namespace std; struct ...
  • 简单多边形 P 的核(kernel),K(p)定义如下:K(p)由多边形内部的点构成,这些点与多边形的任何顶点相连所构成的线段完全包含在 P 中。 一个重要的性质是现,K(p)作为半平面的交集,它或者为空或者为完全包含在P...
  • 题意:求多边形的核的面积 套模板即可 #include <iostream> #include <cstdio> #include <cmath> #define eps 1e-18 using namespace std; const int MAXN = 1555; double a, b, c; ...
  • poj-3130-3335-求多边形的核

    千次阅读 2014-02-18 09:21:12
    多边形的核一般使用半平面交的方法。 如图所示: 在对多边形的每一个边进行延长,然后每条变把多边形分成两半。 图中红色的区域就是核所在的区域。红色区域上的点可以看到多边形的任何一个顶点。 //下面的...
  • 多边形的核:它是平面简单多边形的核是该多边形内部的一个点集该点集中任意一点与多边形边界上一点的连线都处于这个多边形内部。) #include <cstdio> #include <cmath> #include <iostream&...
  • 从AcCry那里找到了一个半平面求多边形的核的比较好的模板,一开始脑袋木了,怎么也看不懂,经过了一个上午的推敲,终于高明白了(以下纯属个人理解),拿来和大家分享一下,另外推荐AcCry的博客,很不错,大家可以去...
  • 半平面交求解多边形的核,当给出点的顺序不同时代码也有所不同。
  • 半平面交 (POJ 1279(第一道半平面NLOGN)完整注释 ) 半平面交的O(NLOGN)算法(转载)求n个半平面的交有三种做法:第一种...由于交出来的都是凸多边形,利用凸多边形的交可以在O(n)时间内完成的性质,将复杂度降为O
  • Poj 3335     #include #include #include #define eps 1e-8 using namespace std; const int MAXN=105;...//此时cCnt为最终切割得到的多边形的顶点数、暂存顶点个数 struct point { do
  • 问给出的多边形中是否存在一点可以观察到整个多边形多边形核的判断,这里只需要判断存不存在,即使是一个点也可以.题目是顺时针给出点 #include <cmath>#include <stdio.h>#include ...
  • //求半平面切割多边形的时候,要先放入4个极限点当整个平面,再求面积,但是由于double只能存1e300+的数,而如果inf=1e15-18就很容易在中间有乘法的计算过程爆炸损失精度,所以inf要根据题意来设置 #include&...
  • poj 1474 半平面交求多边形的核

    千次阅读 2012-05-03 13:55:09
    【题意】 是否能在房间中找到一个位置来安装摄像头,...判断多边形是否存在。用半平面交判断。 【代码】 #include #include #define eps 1e-8 #define oo 1e5 using namespace std; const int maxn=105; struc
  • 半平面,指就是一条直线把一个平面分成了两个半平面…… 如果
  • 计算几何之半平面交、多边形的核

    千次阅读 2016-04-01 17:46:08
    半平面指一个平面一半。比如在二维空间中,一条直线可以把整个平面分为两部分,左边是一个半平面右边是一个半平面。而半平面交就是一堆半平面交集,可以想象成线性规划方程组A0x+B0y+C0>=0,A1x+B1y+C1...
  • poj3130点击打开链接 ... 拿别人模板 poj3335 #include #include #include #include #include #include #define inf 0x7fffffff #define exp 1e-10 #define PI 3.141592654 using namespace std; const int max

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 516
精华内容 206
关键字:

多边形的核