graph_generator

#include <iostream>
#include <vector>
#include <random>

using namespace std;

const int R = 1;
double n, L1, L2, m, k;
struct point {
    double x, y;
};
vector <point> v1;
struct edge {
    point org, dest;
};
vector <edge> v2;
vector <pair <int, int>> v3;

bool belong(point p1, point p2, double a)
{
    double x1 = p1.x, y1 = p1.y, x2 = p2.x, y2 = p2.y;
    return x2 < x1 && x1 < (x2 + a) && y2 < y1 && y1 < (y2 + a);
}

bool obstacle(point p)
{
    double x = p.x, y = p.y;
    double zn = k + L2;
    point p1 = p, p2;
    p2.x = 0, p2.y = 0;
    return (int)(x / zn) != (int)((x + L2) / zn) && (int)(y / zn) != (int)((y + L2) / zn) && belong(p1, p2, L1);
}

bool intersect(edge e1, edge e2)
{
    point p1 = e1.org, p2 = e1.dest, p3 = e2.org, p4 = e2.dest;
    double x1 = p1.x, y1 = p1.y, x2 = p2.x, y2 = p2.y, x3 = p3.x, y3 = p3.y, x4 = p4.x, y4 = p4.y, v1, v2, v3, v4;
    v1 = (x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3);
    v2 = (x4 - x3) * (y2 - y3) - (y4 - y3) * (x2 - x3);
    v3 = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
    v4 = (x2 - x1) * (y4 - y1) - (y2 - y1) * (x4 - x1);
    return v1 * v2 < 0 && v3 * v4 < 0;
}

bool bind(point p1, point p2)
{
    double x1 = p1.x, y1 = p1.y, x2 = p2.x, y2 = p2.y;
    for (int i = 0; i < v2.size(); ++i)
    {
        edge e1, e2 = v2[i];
        e1.org = p1;
        e1.dest = p2;
        if (sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2)) > R || intersect(e1, e2))
            return false;
    }
    return true;
}

int main()
{
    cin >> n >> L1 >> L2 >> m;
    k = (L1 - m * L2) / (m + 1);
    v1.resize(n);
    random_device rnd;
    for (int i = 0; i < n; ++i)
    {
        v1[i].x = (double)rnd() / rnd.max() * L1;
        v1[i].y = (double)rnd() / rnd.max() * L1;
        for (; obstacle(v1[i]);)
        {
            v1[i].x = (double)rnd() / rnd.max() * L1;
            v1[i].y = (double)rnd() / rnd.max() * L1;
        }
    }
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= m; ++j)
        {
            double x0, y0;
            x0 = i * k + (2 * i - 1) * (double)L2 / 2;
            y0 = j * k + (2 * j - 1) * (double)L2 / 2;
            point a[4];
            for (int k = 0; k < 4; ++k)
            {
                a[k].x = x0 + ((k == 1 || k == 4) ? 1 : -1) * (double)L2 / 2;
                a[k].y = y0 + ((k == 1 || k == 2) ? 1 : -1) * (double)L2 / 2;
            }
            for (int k = 0; k < 4; ++k)
            {
                edge e;
                e.org = a[k];
                e.dest = a[(k + 1) % 4];
                v2.push_back(e);
            }
        }
    for (int i = 0; i < n - 1; ++i)
        for (int j = i + 1; j < n; ++j)
            if (bind(v1[i], v1[j]))
                v3.push_back(make_pair(i, j));
    cout << v1.size() << " " << v3.size() << endl;
    for (int i = 0; i < v3.size(); ++i)
        cout << v3[i].first << " " << v3[i].second << endl;
    system("pause");
    return 0;
}