CSU 1812: 三角形和矩形

心已赠人 2022-05-26 11:53 87阅读 0赞

不知道为啥我的程序会错，我是将两个图形的交点以及一个图形顶点在另一个图形内部的点取出来形成一个多边形，结果样例和自己出的数据都过了，结果还是wa  不知道为啥，求好心人给一个样例。

我的代码：

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    const double eps=1e-10;
    struct Point{
    	double x, y;
    	Point(double a=0, double b=0): x(a), y(b){}
    }tri[4], ran[5], poly[1000];
    typedef Point Vector;
    Point ori;
    int cnt=0;
    void init(){
    	cnt=0;
    }
    Point operator + (Point A, Vector B){ return Point(A.x+B.x, A.y+B.y); }
    Vector operator - (Point A, Point B){ return Vector(A.x-B.x, A.y-B.y); }
    Vector operator * (Vector A, double p){ return Vector(A.x*p, A.y*p); }
    bool operator < (Point A, Point B){ return A.x<B.x || A.x==B.x&&A.y<B.y; }
    
    int dcmp(double x){
    	if(fabs(x)<eps)
    		return 0;
    	else
    		return x<0? -1:1;
    }
    
    bool operator == (Point A, Point B){ return dcmp(A.x-B.x)==0 && dcmp(A.y-B.y)==0; }
    
    double Cross(Vector v1, Vector v2){
    	return v1.x*v2.y-v1.y*v2.x;
    }
    
    double Dot(Vector v1, Vector v2){
    	return v1.x*v2.x+v1.y*v2.y;
    }
    
    bool cmp(Point a, Point b){
    	return dcmp(Cross(a-ori, b-ori))>0;
    }
    
    bool SegIntersection(Point a1, Point a2, Point b1, Point b2){
    	double c1=Cross(a2-a1, b1-a1), c2=Cross(a2-a1, b2-a1);
    	double c3=Cross(b2-b1, a1-b1), c4=Cross(b2-b1, a2-b1);
    	return dcmp(c1)*dcmp(c2)<0 && dcmp(c3)*dcmp(c4)<0;
    }
    
    Point GetlineIntersection(Point p, Vector v, Point Q, Vector w){
    	Vector u=p-Q;
    	double t=Cross(w,u)/Cross(v,w);
    	return p+v*t;
    }
    
    bool OnSegment(Point p, Point a1, Point a2){
    	return dcmp(Cross(a1-p, a2-p))==0 && dcmp(Dot(a1-p, a2-p))<0;
    }
    
    bool IsOnSegment(Point p, Point a1, Point a2){
    	return dcmp(Cross(a1-p, a2-p))==0 && dcmp(Dot(a1-p, a2-p))<=0 || a1==p || a2==p;
    }
    
    void GetIntersection(){
    	for(int i=0; i<3; i++)
    	{
    		for(int j=0; j<4; j++)
    		{
    			if(SegIntersection(tri[i], tri[(i+1)%3], ran[j], ran[(j+1)%4]))
    			{
    
    				poly[cnt++]=GetlineIntersection(tri[i], tri[(i+1)%3]-tri[i], ran[j], ran[(j+1)%4]-ran[j]);
    
    			}
    			if(IsOnSegment(tri[i], ran[j], ran[(j+1)%4])){
    				poly[cnt++]=tri[i];
    
    			}
    			if(IsOnSegment(ran[j], tri[i], tri[(i+1)%3])){
    				poly[cnt++]=ran[j];
    
    			}
    
    		}
    	}
    
    }
    
    
    
    
    bool isPointIntri(Point p){
    	int wn=0;
    
    	for(int i=0; i<3; i++)
    	{
    		if(IsOnSegment(p, tri[i], tri[(i+1)%3])) return false;
    
    		int k=dcmp(Cross(tri[(i+1)%3]-tri[i], p-tri[i]));
    		int d1=dcmp(tri[i].y-p.y);
    		int d2=dcmp(tri[(i+1)%3].y-p.y);
    		if(k>0 && d1<=0 && d2>0) wn++;
    		if(k<0 && d2<=0 && d1>0) wn--;
    	}
    
    	if(wn!=0) return true;
    	else return false;
    }
    
    bool isPointInran(Point p){
    	int wn=0;
    
    	for(int i=0; i<4; i++)
    	{
    		if(IsOnSegment(p, ran[i], ran[(i+1)%4])) return false;
    
    		int k=dcmp(Cross(ran[(i+1)%4]-ran[i], p-ran[i]));
    		int d1=dcmp(ran[i].y-p.y);
    		int d2=dcmp(ran[(i+1)%4].y-p.y);
    		if(k>0 && d1<=0 && d2>0) wn++;
    		if(k<0 && d2<=0 && d1>0) wn--;
    	}
    	if(wn!=0) return true;
    	else return false;
    }
    
    void GetIn(){
    
    	for(int i=0; i<3; i++)
    		if(isPointInran(tri[i]))
    		{
    		    poly[cnt++]=tri[i];
    
    		}
    
    	for(int i=0; i<4; i++)
    		if(isPointIntri(ran[i]))
    		{
    		    poly[cnt++]=ran[i];
    		}
    
    }
    
    double GetArea(){
    	double area=0;
        if(cnt<3) return 0;
    	ori=poly[0];
    	sort(poly+1, poly+cnt);
    	cnt = unique(poly, poly+cnt)-poly;
        if(cnt<3) return 0;
    	sort(poly+1, poly+cnt, cmp);
    
    
    	for(int i=1; i<cnt-1; i++)
    		area+=Cross(poly[i]-poly[0], poly[i+1]-poly[0]);
    
    	return area/2;
    }
    
    int main(){
        //freopen("E:/123.txt", "w", stdout);
    	double x1, x2, y1, y2;
    	while(~scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2)){
    		init();
    		tri[0]=Point(x1, y1); tri[1]=Point(x1, y2); tri[2]=Point(x2, y1);
    		ori=tri[0]; sort(tri+1, tri+3, cmp);
    
    
    		scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
    		ran[0]=Point(x1, y1); ran[1]=Point(x1, y2); ran[2]=Point(x2, y2); ran[3]=Point(x2, y1);
    		ori=ran[0]; sort(ran+1, ran+4, cmp);
    
    		GetIntersection();
    		GetIn();
    
    		double area=GetArea();
    		printf("%0.8lf\n", fabs(area));
    	}
    
    
    	return 0;
    }
    
    /*
    1 -1 -2 1
    0 0 2 2
    
    */