写了一个非常裸的暴力,那个步长是我交了N次测出来的。。。
从observer处发出射线,角度从0到360一点一点增加,每次都保存下来这次所遇到的最近的那条边,{zh1}输出即可。
#include <iomanip>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <iterator>
#include <functional>
#include <string>
#include <queue>
#include <numeric>
#include <map>
#include <cmath>
#include <fstream>
using namespace std;
#define eps 1e-10
#define pi 3.141592653
ifstream fin("fence4.in");
ofstream fout("fence4.out");
struct pos_t {
double x, y;
bool operator == (pos_t const &pos) const {
return (fabs(x - pos.x) < eps) && (fabs(y - pos.y) < eps);
}
bool operator < (pos_t const &pos) const {
return (x < pos.x) || ((x == pos.x) && (y < pos.y));
}
};
struct edge_t {
pos_t begin, end;
bool operator == (edge_t const &edge) const {
return (begin == edge.begin) && (end == edge.end);
}
};
struct vector_t {
double x, y;
};
vector<edge_t> edges;
map<pos_t, int> positions;
vector<edge_t> visible_edges;
pos_t observer;
bool operator < (edge_t const &edge1, edge_t const &edge2) {
return (positions[edge1.end] < positions[edge2.end]) || ((positions[edge1.end] == positions[edge2.end]) && (positions[edge1.begin] < positions[edge2.begin]));
}
bool operator > (edge_t const &edge1, edge_t const &edge2) {
return edge2 < edge1;
}
inline
vector_t
edge_to_vector(edge_t const &edge)
{
vector_t vec;
vec.x = edge.end.x - edge.begin.x;
vec.y = edge.end.y - edge.begin.y;
return vec;
}
inline
pos_t
make_pos(double x, double y)
{
pos_t pos;
pos.x = x;
pos.y = y;
return pos;
}
inline
edge_t
make_edge(pos_t const &begin, pos_t const &end)
{
edge_t edge;
edge.begin = begin;
edge.end = end;
return edge;
}
inline
void
add_edge(pos_t &begin, pos_t &end)
{
edges.push_back(make_edge(begin, end));
return;
}
// return the position of the observer
void
scan_data(void)
{
int nr_pos;
vector<pos_t> positions;
fin >> nr_pos;
fin >> observer.x >> observer.y;
positions.resize(nr_pos);
while (nr_pos--) {
fin >> positions[nr_pos].x >> positions[nr_pos].y;
}
reverse(positions.begin(), positions.end());
for (int i = 0; i != positions.size(); ++i) {
::positions[positions[i]] = i;
}
positions.push_back(positions.front());
for (vector<pos_t>::iterator iter = positions.begin(); iter != positions.end() - 1; ++iter) {
pos_t pos1(*iter), pos2(*(iter + 1));
if (::positions[pos1] > ::positions[pos2]) {
swap(pos1, pos2);
}
add_edge(pos1, pos2);
}
return;
}
inline
double
cross_product(vector_t const &vec1, vector_t const &vec2)
{
return vec1.x * vec2.y - vec1.y * vec2.x;
}
inline
pair<double, double>
solve_equation(double a, double b, double c, double d, double e, double f)
{
double t1, t2;
double x, y;
t1 = a * e;
t2 = b * d;
if (fabs(t1 - t2) < eps) {
return make_pair<double, double>(-1e100, -1e100);
}
x = (b * f - e * c) / (t1 - t2);
y = (a * f - d * c) / (t2 - t1);
return make_pair(x, y);
}
template <class TYPE>
inline
TYPE
square(TYPE x)
{
return x * x;
}
inline
double
point_dist(pos_t &pos1, pos_t &pos2)
{
return sqrt(square(pos1.x - pos2.x) + square(pos1.y - pos2.y));
}
inline
double
vector_length(vector_t &vec)
{
return sqrt(square(vec.x) + square(vec.y));
}
inline
double
dist_to_edge(pos_t &pos, edge_t &edge)
{
edge_t edge1(make_edge(pos, edge.begin)), edge2(make_edge(pos, edge.end));
vector_t vec1(edge_to_vector(edge1)), vec2(edge_to_vector(edge2)), vec3(edge_to_vector(edge));
return cross_product(vec1, vec2) / vector_length(vec3);
}
inline
bool
different_side(edge_t &edge, pos_t pos1, pos_t pos2)
{
vector_t vec1(edge_to_vector(edge)), vec2(edge_to_vector(make_edge(edge.begin, pos1))), vec3(edge_to_vector(make_edge(edge.begin, pos2)));
double cp1(cross_product(vec1, vec2)), cp2(cross_product(vec1, vec3));
return cp1 * cp2 < 0;
}
inline
bool
edge_cross(edge_t &edge1, edge_t &edge2)
{
if (different_side(edge1, edge2.begin, edge2.end) && different_side(edge2, edge1.begin, edge1.end)) {
return true;
}
return false;
}
bool
validate(void)
{
for (vector<edge_t>::iterator iter = edges.begin(); iter != edges.end(); ++iter) {
for (vector<edge_t>::iterator iter2 = iter + 1; iter2 != edges.end(); ++iter2) {
if (edge_cross(*iter, *iter2)) {
return false;
}
}
}
return true;
}
bool
visible_edge(edge_t &constructed_edge, edge_t &selected_edge)
{
vector<pair<double, edge_t> > vec;
for (vector<edge_t>::iterator iter = edges.begin(); iter != edges.end(); ++iter) {
double ax(iter->begin.x), bx(iter->end.x), cx(constructed_edge.begin.x), dx(constructed_edge.end.x);
double ay(iter->begin.y), by(iter->end.y), cy(constructed_edge.begin.y), dy(constructed_edge.end.y);
pair<double, double> t;
double i, j;
pos_t intersect_point;
if (!edge_cross(constructed_edge, *iter)) {
continue;
}
t = solve_equation(bx - ax, cx - dx, ax - cx, by - ay, cy - dy, ay - cy);
i = t.first;
j = t.second;
intersect_point.x = ax + (bx - ax) * i;
intersect_point.y = ay + (by - ay) * i; // ??????
if (fabs(intersect_point.x - -1e100) < eps) {
continue;
}
vec.push_back(make_pair(point_dist(intersect_point, observer), *iter));
}
if (!vec.size()) {
return false;
}
sort(vec.begin(), vec.end());
selected_edge = vec.front().second;
return true;
}
void
build_solution(void)
{
pos_t dest;
map<edge_t, bool> exists;
dest.x = observer.x + 10000;
for (double angle = -pi / 2 + 0.000001; angle <= pi / 2; angle += 0.00015) {
edge_t constructed_edge, selected_edge;
dest.y = 10000 * tan(angle - pi) + observer.y;
constructed_edge = make_edge(observer, dest);
if (visible_edge(constructed_edge, selected_edge)) {
double new_angle(angle);
if (!exists[selected_edge]) {
visible_edges.push_back(selected_edge);
exists[selected_edge] = true;
}
}
}
dest.x = observer.x - 10000;
for (double angle = -pi / 2 + 0.000001; angle <= pi / 2; angle += 0.00015) {
edge_t constructed_edge, selected_edge;
dest.y = (10000 * tan(angle - pi) + observer.y);
constructed_edge = make_edge(observer, dest);
if (visible_edge(constructed_edge, selected_edge)) {
double new_angle(angle);
if (!exists[selected_edge]) {
visible_edges.push_back(selected_edge);
exists[selected_edge] = true;
}
visible_edges.push_back(selected_edge);
}
}
sort(visible_edges.begin(), visible_edges.end());
visible_edges.erase(unique(visible_edges.begin(), visible_edges.end()), visible_edges.end());
return;
}
void
dump_solution(void)
{
fout << visible_edges.size() << endl;
for (vector<edge_t>::iterator iter = visible_edges.begin(); iter != visible_edges.end(); ++iter) {
fout << fixed << setprecision(0) << iter->begin.x << " " << iter->begin.y << " " << iter->end.x << " " << iter->end.y << endl;
}
return;
}
int
main()
{
scan_data();
build_solution();
dump_solution();
return 0;
}