1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114
| #include <bits/stdc++.h> #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--)
using namespace std;
const string filename = "fence4";
void usefile(){ freopen((filename+".in").c_str(),"r",stdin); freopen((filename+".out").c_str(),"w",stdout); }
pair<int,int> p; pair<int,int> P[210]; int N;
double cross(pair<double,double> a,pair<double,double> b){ return a.first*b.second-a.second*b.first; }
pair<double,double> operator + (pair<double,double> a,pair<double,double> b) { return {a.first+b.first,a.second+b.second}; }
pair<double,double> operator - (pair<double,double> a,pair<double,double> b) { return {a.first-b.first,a.second-b.second}; }
bool isIntersect(pair<pair<double,double>,pair<double,double>> line1,pair<pair<double,double>,pair<double,double>> line2){ return !( (cross(line1.first -line2.first,line2.second-line2.first) > 0) == (cross(line1.second-line2.first,line2.second-line2.first) > 0) || (cross(line2.first -line1.first,line1.second-line1.first) > 0) == (cross(line2.second-line1.first,line1.second-line1.first) > 0) );
}
bool isValid(){ rep(i,0,N){ rep(j,i+2,N){ if(i == 0 && j == N-1)continue; if(isIntersect({P[i],P[i+1]}, {P[j],P[(j+1)%N]})){ return false; } } } return true; }
bool isColine(int idx){ return cross(P[idx]-P[(idx+1)%N],p) == cross(P[idx],P[(idx+1)%N]); }
bool isSeen(int idx){ int x1 = P[idx].first; int y1 = P[idx].second; int nsegments = 1000; rep(i,1,nsegments){ pair<double,double> point_ = { x1 + i * 1.0 / nsegments * (P[(idx + 1) % N].first - x1), y1 + i * 1.0 / nsegments * (P[(idx + 1) % N].second - y1)}; bool blocked = false; rep(j,0,N){ if(j == idx) { continue; } if(isIntersect({p,point_}, {P[j],P[(j+1)%N]})){ blocked = true; break; } } if(!blocked) { return true; } } return false; }
vector<int> ans; int main(){ usefile(); scanf("%d", &N); scanf("%d %d", &p.first,&p.second); rep(i,0,N){ scanf( "%d %d", &P[i].first, &P[i].second); } if(!isValid()) { printf( "NOFENCE\n"); return 0; } rep(i,0,N){ if(!isColine(i) && isSeen(i)) { ans.push_back(i); } } if(ans.size() >= 2 && ans[ans.size() - 2] == N - 2){ ans[ans.size() - 2] = N - 1; ans[ans.size() - 1] = N - 2; } printf("%d\n", int(ans.size())); rep(i,0,ans.size()){ if(ans[i] == N - 1) { printf("%d %d %d %d\n", P[0].first, P[0].second, P[ans[i]].first, P[ans[i]].second); }else{ printf( "%d %d %d %d\n", P[ans[i]].first, P[ans[i]].second, P[ans[i] + 1].first, P[ans[i] + 1].second); } } return 0; }
|