Checking whether the fence is valid is fairly simple. We just check whether one line segment intersects some other line segment (excluding the neighbor segments).

Afterwards, it is the tricky part. We have to find all the visible segments. How can we do that?

Let the observer be the point P and some random line segment be Q where its end points are respectively A and B.

We will partition the line in 250 parts (from A + EPS to B – EPS). Then we will build every possible line to the part points (i.e. the line P – (A + EPS*2)). Then we will just check whether the newly created line intersects some of the fence segments. If it doesn’t, the line segment Q is visible to P.

And also, we will have to use in our calculations as well. For example, in our check whether the value is nearly 0.

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
int n;
#define EPS 0.05
#define PARTITION 250.0
struct point {
double x;
double y;
};
struct line {
point a;
point b;
};
FILE * in, * out;
point p[202];
line l[202];
point observer;
vector<line> ans;
point makePoint(double x, double y) {
point tmp;
tmp.x = x;
tmp.y = y;
return tmp;
}
line makeLine(point a, point b) {
line tmp;
tmp.a = a;
tmp.b = b;
return tmp;
}
point operator -(point a, point b) {
a.x -= b.x;
a.y -= b.y;
return a;
}
point operator +(point a, point b) {
a.x += b.x;
a.y += b.y;
return a;
}
line getOrderedLine (line a) {
if (a.a.y > a.b.y) {
point tmp = a.a;
a.a = a.b;
a.b = tmp;
}
if (a.a.y == a.b.y && a.a.x > a.b.x) {
point tmp = a.a;
a.a = a.b;
a.b = tmp;
}
return a;
}
double cross(point a, point b) {
return a.x*b.y - a.y*b.x;
}
bool nearlyZero(double value) {
if (value>=-EPS && value<=0) {
return true;
}
return false;
}
void printPoint (point a) {
cout << "(" << a.x << " " << a.y << ")";
}
void printLine(line a) {
printPoint(a.a);
cout << " - ";
printPoint(a.b);
cout << endl;
}
bool segmentIntersect(line a, line b) {
a = getOrderedLine(a);
b = getOrderedLine(b);
double first = cross(a.b-a.a,b.a-a.a)*cross(a.b-a.a,b.b-a.a);
double second = cross(b.b-b.a,a.a-b.a)*cross(b.b-b.a,a.b-b.a);
if (nearlyZero(first) && nearlyZero(second)) {
if (a.a.y!=a.b.y && b.a.y != b.b.y) {
if (((a.a.y <= b.a.y && a.b.y >= b.a.y) || (b.a.y <= a.a.y && a.a.y <= b.b.y))) return true;
} else {
if ((a.a.x <= b.a.x && a.b.x >= b.a.x) || (b.a.x <= a.a.x && a.a.x <= b.b.x)) return true;
}
return false;
}
if (first > EPS) return false;
if (second > EPS) return false;
return true;
}
bool canSeeLine(line a, int ignoreIndex) {
point delta = makePoint((a.b.x-a.a.x)/PARTITION, (a.b.y-a.a.y)/PARTITION);
line cpy = a;
for (int i = 0; i < PARTITION-1; ++i) {
a.a = a.a+delta;
line check = makeLine(observer, a.a);
bool blocked = false;
int j = 0;
for (j = 0; j < n && !blocked; ++j) {
if (j == ignoreIndex) continue;
if (segmentIntersect(l[j],check)) {
blocked = true;
}
}
if (!blocked) {
if (ignoreIndex==19) {
printLine(cpy);
printLine(a);
}
return true;
}
}
return false;
}
void solve() {
for (int i = 0; i < n-1; ++i) {
for (int j = i+2; j < n-1; ++j) {
if (segmentIntersect(l[i],l[j])) {
printLine(l[i]);
printLine(l[j]);
return;
}
}
}
for (int i = 0; i < n; ++i) {
if (canSeeLine(getOrderedLine(l[i]),i)) {
ans.push_back(l[i]);
}
}
}
int getPointIndex(point a) {
for (int i = 0; i < n; ++i) {
if (a.x == p[i].x && a.y == p[i].y) return i;
}
}
bool comparator(line a, line b) {
int indexA = getPointIndex(a.b);
int indexB = getPointIndex(b.b);
if (indexA != indexB) return indexA < indexB;
return getPointIndex(a.a) < getPointIndex(b.a);
}
int main() {
in = fopen("fence4.in","r");
int a,b;
fscanf(in,"%d%d%d",&n,&a,&b);
observer = makePoint(a,b);
for (int i = 0; i < n; ++i) {
fscanf(in,"%d %d",&a,&b);
p[i] = makePoint((double)a,(double)b);
}
p[n] = p[0];
for (int i = 0; i < n-1; ++i) {
l[i] = makeLine(p[i],p[i+1]);
}
l[n-1] = makeLine(p[0],p[n-1]);
fclose(in);
solve();
out = fopen("fence4.out","w");
if (ans.size() == 0) {
fprintf(out, "NOFENCEn");
} else {
fprintf(out,"%dn", ans.size());
sort(ans.begin(),ans.end(), comparator);
for (int i = 0; i < ans.size(); ++i) {
fprintf(out,"%d %d %d %dn",(int)ans[i].a.x,(int)ans[i].a.y,(int)ans[i].b.x,(int)ans[i].b.y);
}
}
fclose(out);
return 0;
}