Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
你家多边形有边共线???不看讨论根本想不到好么,还以为是精度問題。 #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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator