| ||||||||||
| 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