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 KatrineYang at 2017-01-19 04:53:16 on Problem 1584 and last updated at 2017-01-19 04:53:48
不看讨论根本想不到好么,还以为是精度問題。
#include <iostream>
#include <cmath>
using namespace std;

struct pt{
	double x,y;
};

pt pts[1000000], O;
double r;
int n;

int getRx(int i1){
	int i2 = (i1+1)%n, i3 = (i2+1)%n;
	pt xl1, xl2;
	xl1.x = pts[i2].x - pts[i1].x, xl1.y = pts[i2].y-pts[i1].y;
	xl2.x = pts[i3].x - pts[i2].x, xl2.y = pts[i3].y-pts[i2].y;
	if(xl1.x*xl2.y - xl2.x*xl1.y > 0) return 1;
	else if(xl1.x*xl2.y - xl2.x*xl1.y < 0) return -1;
	return 0;
}



double area2(pt &p1, pt &p2, pt &p3){
	return p1.x * p2.y + p2.x * p3.y + p3.x * p1.y - p1.y * p2.x - p2.y * p3.x - p3.y * p1.x;
}

double dis(pt &p1, pt &p2){
	return sqrt((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y));
}

int getRx(pt &p1, pt &p2, pt &p3){
	return (area2(p1,p2,p3)>0) ? 1 : -1;
}

int main() {
	while(1){
		cin >> n;
		if(n < 3) break;
		cin >> r >> O.x >> O.y;
		for(int i = 0; i < n; i++){
			cin >> pts[i].x >> pts[i].y;
		}
		bool ky = true, tu = true;
		int rx = 0;
		for(int i = 0; i < n; i++){
			int xrx = getRx(i);
			if(!xrx) continue;
			if(rx * xrx < 0){
				ky = false;
				tu = false;
				goto gaodingle;
			}
			rx = xrx;
		}
		rx = 0;
		for(int i = 0; i < n; i++){
			int xrx = getRx(O, pts[i], pts[(i+1)%n]);
			if(rx * xrx < 0){
				ky = false;
				goto gaodingle;
			}
			rx = xrx;
		}
		for(int i = 0; i < n; i++){
			double dist = abs(area2(O, pts[i], pts[(i+1)%n])) / dis(pts[i], pts[(i+1)%n]);
			if(dist < r){
				ky = false;
				goto gaodingle;
			}
		}
		gaodingle:
		if(!tu) cout << "HOLE IS ILL-FORMED" << endl;
		else if(!ky) cout << "PEG WILL NOT FIT" << endl;
		else cout << "PEG WILL FIT" << endl;
	}
	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