10867 - Cutting a Polygon

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
zool007
New poster
Posts: 2
Joined: Thu Nov 22, 2012 7:52 am

10867 - Cutting a Polygon

Post by zool007 » Fri Jul 19, 2013 4:16 pm

help I get WA many times.
what my code does is get all intersections of the line and the polygon. then sort the intersections by x. for every consecutive point, I check whether the midpoint of the line formed by the consecutive points is inside the polygon or in the perimeter of the polygon. if it is, then I just add the answer by the length of the line formed by the consecutive points.
here is my code:

Code: Select all

#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#include<iostream>

using namespace std;

const double eps = 1e-8;
const double ep = 1e-12;
int n;
struct Point{
	double x,y;
	bool operator<(const Point &o) const{
		double dx = x-o.x;
		if(abs(dx)<eps)
			return y<o.y;
		return x<o.x;
	}
	bool operator==(const Point &o) const{
		return abs(x-o.x)<eps && abs(y-o.y)<eps;
	}
};

double slope(Point a, Point b){
	double dx = a.x-b.x;
	double dy = a.y-b.y;
	if(abs(dx)<eps)return 1e20;
	else return dy/dx;
}

double dist(Point a,Point b){
	double dx = a.x-b.x;
	double dy = a.y-b.y;
	return sqrt(dx*dx+dy*dy);
}

void checkForIntersections(Point a, Point b, Point c, Point d, vector<Point> &vec){
	Point p1 = a;
	Point p2 = b;
	Point p3 = c;
	Point p4 = d;
				if(b<a)
				{
					p1 = b;
					p2 = a;
				}
				/*if(j!=0){
					arr[j].x += 10*eps;
					arr[j].y +=10*eps;
				}*/
				if(d<c){
					p3 = d;
					p4 = c;
				}
	Point ans;
	double minx = min(p3.x,p4.x);
	double maxx = max(p3.x,p4.x);
	double miny = min(p3.y,p4.y);
	double maxy = max(p3.y,p4.y);
	double minx2 = min(p1.x,p2.x);
	double maxx2 = max(p1.x,p2.x);
	double miny2 = min(p1.y,p2.y);
	double maxy2 = max(p1.y,p2.y);
	if(p1.x-p2.x == 0 && p3.y-p4.y == 0){
		ans.x = p1.x; ans.y = p3.y;
	}
	else if(p3.x-p4.x == 0 && p1.y-p2.y == 0){
		ans.x = p3.x; ans.y = p1.y;
	}
	else {
		double D = (p1.x-p2.x) * (p3.y-p4.y) 
			 - (p1.y-p2.y) * (p3.x-p4.x);
		if(abs(D)<eps){
			if(abs(slope(p3,p2)-slope(p3,p4))<eps){
				if(p3<p1)
					ans = p1;
				else
					ans = p3;
				Point ans2;
				if(p4<p2)
					ans2 = p4;
				else
					ans2 = p2;
				//if(j!=0 || !(ans==a))
				if(ans<ans2 || ans==ans2){
					vec.push_back(ans);
					
					vec.push_back(ans2);
				}
				
				//printf("zero %.3f %.3f %.3f %.3f inside %.3f %.3f %.3f %.3f\n",ans.x,ans.y,ans2.x,ans2.y,c.x,c.y,d.x,d.y);
			}
			
			return;
		}
		else{
			double A = p1.x * p2.y - p1.y * p2.x;
			double B = p3.x * p4.y - p3.y * p4.x;
			ans.x = (A*(p3.x-p4.x) 
						  - B*(p1.x-p2.x))/D;
			ans.y = (A*(p3.y-p4.y)
						  - B*(p1.y-p2.y))/D;
		}
	}
	if(ans.x+eps>=minx && ans.x<=maxx+eps && ans.y+eps>=miny && ans.y <=maxy+eps && ans.x+eps>=minx2 && ans.x<=maxx2+eps && ans.y+eps>=miny2 && ans.y <=maxy2+eps){
		vec.push_back(ans);
	}
	//else printf("%.3f %.3f did not intersect\n",ans.x,ans.y);
	
}

bool inside(Point o, Point poly[]) {
	int j=n-1;
	bool oddNodes=false;
	for (int i=0; i<n; i++) {
		if ((poly[i].y< o.y && poly[j].y>=o.y
		||   poly[j].y< o.y && poly[i].y>=o.y)
		&&  (poly[i].x<=o.x || poly[j].x<=o.x)) {
		  oddNodes^=(poly[i].x+(o.y-poly[i].y)/(poly[j].y-poly[i].y)*(poly[j].x-poly[i].x)<o.x); }
		j=i;
	}
	return oddNodes;
}

bool inPerimeter(Point o, Point p[]){
	
	for(int i = 0;i<n;i++){
		Point a = p[i];
		Point b = p[(i+1)%n];
		double minx = min(a.x,b.x);
		double maxx = max(a.x,b.x);
		double miny = min(a.y,b.y);
		double maxy = max(a.y,b.y);
		if(o.x+eps>=minx && o.x<=maxx+eps && o.y+eps>=miny && o.y<=maxy+eps && abs(slope(a,o)-slope(b,o))<eps)
			return true;
	}
	return false;
}

int main(){
	int m;
	while(scanf("%d %d\n",&n,&m) &&n){
		Point arr[n];
		for(int i = 0;i<n;i++)
			scanf("%lf %lf\n",&arr[i].x,&arr[i].y);
		for(int i = 0;i<m;i++){
			vector<Point> vec;
			Point a,b;
			scanf("%lf %lf %lf %lf\n",&a.x,&a.y,&b.x,&b.y);
			vec.push_back(a);
			vec.push_back(b);
			for(int j = 0;j<n;j++){
				Point c = arr[j];
				Point d = arr[(j+1)%n];
				
				checkForIntersections(a,b,c,d,vec);
			}
			int k = vec.size();
			double ans = 0.0;
			sort(vec.begin(),vec.end());
			//printf("\n");
			//or(int j = 0;j<k;j++)
			//	printf("vec: %.3f %.3f\n",vec.at(j).x,vec.at(j).y);
			for(int j = 0;j<k-1;j++){
				//printf("vec: %.3f %.3f\nvec: %.3f %.3f\n",vec.at(j).x,vec.at(j).y,vec.at(j+1).x,vec.at(j+1).y);
				Point xx = vec.at(j);
				Point yy = vec.at(j+1);
				Point mid;
				mid.x = 0.5*(xx.x+yy.x);
				mid.y = 0.5*(xx.y+yy.y);
				if(inside(mid,arr) || inPerimeter(mid,arr))
					ans+=dist(vec.at(j),vec.at(j+1));
			}
			printf("%.3f\n",ans+eps);
		}
	}
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10867 - Cutting a Polygon

Post by brianfry713 » Thu Jul 25, 2013 2:27 am

You could be having precision errors. To see if a floating point value is equal to 0, don't use value == 0, use something like fabs(value) < EPS. Also try this method for finding the intersection point:
http://en.wikipedia.org/wiki/Line-line_intersection
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 108 (10800-10899)”