Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Единственный способ попасть в зал круглых столов - пройти через колонный коридор. Стены коридора
- // изображаются на карте прямыми линиями, которые параллельны оси OY системы координат.
- // Вход в коридор находится снизу, а выход из коридора в зал - сверху. В коридоре есть цилиндрические
- // (на карте круглы) колонны одинакового радиуса R.
- // Разработайте алгоритм, который по информации о размерах коридора и размещения колонн определяет диаметр
- // наибольшего из круглых столов, который можно пронести через такой коридор, сохраняя поверхность горизонтальной.
- #include <iostream>
- #include <vector>
- #include <set>
- #include <algorithm>
- #include <cmath>
- #include <cstdio>
- using namespace std;
- class MyGraph {
- public:
- // конструктор
- MyGraph();
- // деструктор
- ~MyGraph();
- // считываем все входные данные
- void ReadData();
- // строим граф
- void BuildGraph();
- // dfs для поиска компонент связности
- void DfsFindSCC(int v, vector <int> &component);
- // поиск компонент сильной связности
- void FindSCC();
- // проверка, можем ли мы пронести стол
- bool CheckComponents();
- // бинарный поиск по ответу (диаметру стола)
- void BinSearch();
- private:
- // левая стенка
- int xL;
- // правая стенка
- int xR;
- // радиус колонн
- int r;
- // кол-во колонн
- int n;
- // набор всех колонн и их проекций
- vector <pair <int, int> > vertex;
- // диаметр стола
- double D;
- // граф
- vector <vector <int> > g;
- // массив посещенных вершин
- vector <bool> used;
- // массив, в котором хранятся компоненты сильной связности
- vector <vector <int> > components;
- // кол-во вершин
- int V;
- };
- MyGraph::MyGraph() {
- }
- MyGraph::~MyGraph() {
- g.clear();
- used.clear();
- components.clear();
- vertex.clear();
- }
- void MyGraph::ReadData() {
- set<int> setOfY;
- cin >> xL >> xR;
- cin >> r;
- xL -= r;
- xR += r;
- cin >> n;
- for( int i = 0; i < n; i++ ) {
- int x, y;
- cin >> x >> y;
- vertex.push_back( make_pair(x, y) );
- if( setOfY.count(y) == 0 ) {
- setOfY.insert(y);
- vertex.push_back( make_pair(xL, y) );
- vertex.push_back( make_pair(xR, y) );
- }
- }
- V = vertex.size();
- }
- void MyGraph::BuildGraph() {
- g.assign( V, vector <int>(0) );
- for( int i = 0; i < V; i++ )
- for( int j = 0; j < V; j++ ) {
- int dist = (vertex[i].first - vertex[j].first) * (vertex[i].first - vertex[j].first);
- dist += (vertex[i].second - vertex[j].second) * (vertex[i].second - vertex[j].second);
- if( i != j && dist < D*D ) {
- g[i].push_back(j);
- }
- }
- }
- void MyGraph::DfsFindSCC(int v, vector <int> &component) {
- used[v] = true;
- component.push_back(v);
- for( int i = 1; i < g[v].size(); i++ ) {
- if( !used[g[v][i]] ) {
- DfsFindSCC( g[v][i], component );
- }
- }
- }
- void MyGraph::FindSCC() {
- components.clear();
- used.assign(V, false);
- for( int i = 0; i < V; i++ ) {
- int v = i;
- if( !used[v] ) {
- vector <int> component;
- DfsFindSCC(v, component);
- components.push_back(component);
- }
- }
- }
- bool MyGraph::CheckComponents() {
- bool answer = true;
- for( int i = 0; i < components.size(); i++ ) {
- bool on_right_wall = false;
- bool on_left_wall = false;
- for( int j = 0; j < components[i].size(); j++ ) {
- int v = components[i][j];
- if( vertex[v].first == xL ) {
- on_left_wall = true;
- }
- if( vertex[v].first == xR ) {
- on_right_wall = true;
- }
- }
- if( on_right_wall && on_left_wall ) {
- return false;
- }
- }
- return answer;
- }
- void MyGraph::BinSearch() {
- double left = 0.000;
- double right = xR - xL;
- while( right - left > 0.0001 ) {
- double m = (left + right) / 2;
- D = m;
- BuildGraph();
- FindSCC();
- bool ans = CheckComponents();
- if( ans ) {
- left = m;
- } else {
- right = m;
- }
- }
- cout << fixed;
- cout.precision(3);
- cout << abs(D - 2*r);
- }
- int main() {
- MyGraph g;
- g.ReadData();
- g.BinSearch();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement