Closed Fences_专业打酱油_百度空间
写了一个非常裸的暴力,那个步长是我交了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;
}


郑重声明:资讯 【Closed Fences_专业打酱油_百度空间】由 发布,版权归原作者及其所在单位,其原创性以及文中陈述文字和内容未经(企业库qiyeku.com)证实,请读者仅作参考,并请自行核实相关内容。若本文有侵犯到您的版权, 请你提供相关证明及申请并与我们联系(qiyeku # qq.com)或【在线投诉】,我们审核后将会尽快处理。
—— 相关资讯 ——