Входные данные
Целое n (1 <= n <= 100) -- количество вершин в многоугольнике. Затем координаты вершин. Все его вершины различны. Никакие две подряд идущие стороны не лежат на одной прямой. Все стороны имеют положительную длину.
Выходные данные
Выводит в первую строку количество отрезков в обходе внешней грани. Далее выводит все вершины внешней грани в искомом порядке. Искомая ломаная не имеет самопересечений (хотя может иметь самокасания). Все стороны имеют положительную длину. Никакие две подряд идущие стороны не лежат на одной прямой. При обходе границы, внутренность всегда находится по левую сторону.
| Код | #include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
typedef pair<double,double> point;
vector<point> pt;
int cur_i;
const double EPS = 1E-7;
bool cmp (int i, int j)
{
return
atan2 (pt[i].second-pt[cur_i].second+0.0, pt[i].first-pt[cur_i].first+0.0) <
atan2 (pt[j].second-pt[cur_i].second+0.0, pt[j].first-pt[cur_i].first+0.0) - EPS;
}
bool cmp_pt (point a, point b)
{
return a.first < b.first-EPS || abs (a.first-b.first) < EPS && a.second < b.second-EPS;
}
bool eq_pt (point a, point b)
{
return abs (a.first-b.first) < EPS && abs (a.second-b.second) < EPS;
}
bool in (double n, double a, double b)
{
return n >= min(a,b)-EPS && n <= max(a,b)+EPS;
}
vector < vector<int> > g;
vector < vector<char> > used;
vector<int> res;
void rec (int i, int j)
{
res.push_back (i);
size_t k;
for (k=0; k<g[j].size(); ++k)
if (g[j][k] == i)
break;
if (++k == g[j].size())
k = 0;
if (!used[j][k])
{
used[j][k] = true;
rec (j, g[j][k]);
}
}
int main()
{
int n;
cin >> n;
if (n < 3) throw;
vector<point>a (n);
for (int i=0; i<n; ++i)
cin >> a[i].first >> a[i].second;
vector < pair<point,point> > b (n);
for (int i=0; i<n; ++i)
{
point left = a[i], right = a[i==n-1 ? 0 : i+1];
if (cmp_pt (right, left))
swap (left, right);
b[i] = make_pair (left, right);
}
map<point,int> pt_id;
for (int i=0; i<n; ++i)
{
point left = b[i].first, right = b[i].second;
vector<point> inters;
inters.push_back (left);
inters.push_back (right);
for (int j=0; j<n; ++j)
if (i != j)
{
point left2 = b[j].first, right2 = b[j].second;
double a1 = left.second-right.second, b1 = right.first-left.first,
c1 = right.first*left.second-left.first*right.second;
double a2 = left2.second-right2.second, b2 = right2.first-left2.first,
c2 = right2.first*left2.second-left2.first*right2.second;
if (abs (a1*b2-a2*b1) < EPS)
{
if (abs (a1*c2-a2*c1) < EPS && abs (b1*c2-b2*c1) < EPS)
{
if (in (left2.first, left.first, right.first) && in (left2.second, left.second, right.second))
inters.push_back (left2);
if (in (right2.first, left.first, right.first) && in (right2.second, left.second, right.second))
inters.push_back (right2);
}
}
else
{
double x = (c1*b2-c2*b1) / (a1*b2-a2*b1);
double y = (a1*c2-a2*c1) / (a1*b2-a2*b1);
if (in (x, left.first, right.first) && in (x, left2.first, right2.first) &&
in (y, left.second, right.second) && in (y, left2.second, right2.second))
inters.push_back (point (x, y));
}
}
sort (inters.begin(), inters.end(), cmp_pt);
inters.erase (unique (inters.begin(), inters.end(), eq_pt), inters.end());
for (size_t j=0; j<inters.size()-1; ++j)
{
point a = inters[j], b = inters[j+1];
if (!pt_id.count(a)) { pt_id[a] = pt_id.size(); g.push_back (vector<int>()); }
if (!pt_id.count(b)) { pt_id[b] = pt_id.size(); g.push_back (vector<int>()); }
int ia = pt_id[a], ib = pt_id[b];
while (pt.size() < pt_id.size())
pt.push_back (point());
pt[ia] = a;
pt[ib] = b;
g[ia].push_back (ib);
g[ib].push_back (ia);
}
}
n = pt_id.size();
for (int i=0; i<n; ++i)
{
sort (g[i].begin(), g[i].end());
g[i].erase (unique (g[i].begin(), g[i].end()), g[i].end());
cur_i = i;
sort (g[i].begin(), g[i].end(), cmp);
}
int result = 0;
used.resize (n);
for (int i=0; i<n; ++i)
used[i].assign (g[i].size(), false);
int up = 0;
for (int i=1; i<n; ++i)
if (pt[i].second > pt[up].second || pt[i].second == pt[up].second && pt[i].first < pt[up].first)
up = i;
used[up][0] = true;
rec (up, g[up][0]);
for (size_t i=0; i<res.size(); ++i)
{
point b = pt[res[i]], c = pt[res[(i+1)%res.size()]], a = pt[res[i?i-1:res.size()-1]];
if (abs ( (b.first-a.first)*(c.second-a.second) - (b.second-a.second)*(c.first-a.first) ) < EPS)
res.erase (res.begin()+i--);
}
cout << res.size() << '\n';
for (size_t i=0; i<res.size(); ++i)
cout << pt[res[i]].first << ' ' << pt[res[i]].second << '\n';
} |
|
)