CSES - Aalto Competitive Programming 2024 - wk10 - Mon - Results
Submission details
Task:6G network
Sender:minghao
Submission time:2024-11-11 17:50:00 +0200
Language:C++ (C++20)
Status:COMPILE ERROR

Compiler report

input/code.cpp: In function 'void Union(int, int)':
input/code.cpp:104:8: error: reference to 'size' is ambiguous
  104 |     if(size[x] < size[y])
      |        ^~~~
In file included from /usr/include/c++/11/string:54,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from input/code.cpp:1:
/usr/include/c++/11/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/11/bits/range_acces...

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=10005;
const double EPS = 1e-8, INF=1e20, PI = acos(-1.0);

inline int Sign(const double& x)
{
    if(fabs(x) < EPS)   return 0;
    if(x < 0)           return -1;
    else                return 1;
}

struct Point
{
    double x_, y_;
    Point(){}
    Point(double x, double y)
    {
        x_ = x;
        y_ = y;
    }
    void Input() {
        scanf("%lf%lf", &x_, &y_);
    }

    bool operator == (const Point& P)const {
        return Sign(x_ - P.x_) == 0 && Sign(y_ - P.y_) == 0;
    }
    bool operator < (const Point& P)const {
        return Sign(x_ - P.x_) == 0? Sign(y_ - P.y_)<0 : x_<P.x_;
    }
    double operator ^ (const Point& P)const {
        return x_*P.y_ - y_*P.x_;
    }
    double operator * (const Point& P)const {
        return x_*P.x_ + y_*P.y_;
    }
    Point operator + (const Point& P)const {
        return Point(x_+P.x_, y_+P.y_);
    }
    Point operator - (const Point& P)const {
        return Point(x_-P.x_, y_-P.y_);
    }
    Point operator * (const double& k)const {
        return Point(x_*k, y_*k);
    }
    Point operator / (const double& k)const {
        return Point(x_/k, y_/k);
    }

    double len() {
        return hypot(x_, y_);
    }
    double dis(Point P) {
        return hypot(x_ - P.x_, y_ - P.y_);
    }
};

struct Line
{
    Point s_, e_;
    Line(){}
    Line(Point s, Point e)
    {
        s_ = s;
        e_ = e;
    }
    Line(Point p, double angle)
    {
        s_ = p;
        if(Sign(angle - PI/2) == 0) {
            e_ = (s_ + Point(0, 1));
        } else {
            e_ = (s_ + Point(1, tan(angle)));
        }
    }
    // 3(O) 2(R) 1(L)
    int Relation(Point p) 
    {
        int c = Sign((p-s_)^(e_-s_));
        if(c < 0)       return 1;
        else if(c > 0)  return 2;
        else            return 3;
    }
    bool OnSeg(Point p) {
        return Sign((p-s_)^(e_-s_)) == 0 && Sign((p-s_)*(p-e_)) <= 0;
    }
};
// Union&Find Start
int father[N], size[N];
 
int Find(int x)
{
    if(father[x]==x)
        return x;
    return father[x]=Find(father[x]);
}
void Union(int x, int y)
{
    x = Find(x), y=Find(y);
    if(x==y)
        return;
    if(size[x] < size[y])
        std::swap(x, y);
    father[y] = x;
    size[x] += size[y];
}
// Union&Find End

struct Polygon
{
    int n_;
    Point p_[N];
    Line l_[N];
    void Input(int n)
    {
        n_ = n;
        for(int i=0; i<n_; i++)
            p_[i].Input();
        InitLines();
    }
    void InitLines()
    {
        for(int i=0; i<n_; i++)
            l_[i] = Line(p_[i], p_[(i+1)%n_]);
    }

    double Area()
    {
        double ret = 0;
        for(int i=0; i<n_; i++)
            ret += (p_[i] ^ p_[(i+1)%n_]);
        return fabs(ret)/2;
    }
    // 3(P) 2(E) 1(I) 0(O)
    int Relation(Point p)
    {
        for(int i=0; i<n_; i++)
            if(p_[i] == p)      return 3;
        for(int i=0; i<n_; i++)
            if(l_[i].OnSeg(p))  return 2;
        int cnt = 0;
        for(int i=0; i<n_; i++)
        {
            int j = (i+1)%n_;
            int k = Sign((p-p_[j])^(p_[i]-p_[j]));
            int u = Sign(p_[i].y_ - p.y_);
            int v = Sign(p_[j].y_ - p.y_);
            if(k > 0 && u < 0 && v >= 0) cnt++;
            if(k < 0 && v < 0 && u >= 0) cnt--;
        }
        return cnt != 0;
    }

    double dist[N][N];
    void Calc()
    {
        for(int i=0; i<n; i++)
            father[i] = i;
        priority_queue<Edge> q;
        for(int i=0; i<n_; i++)
            for(int j=i; j<n_; j++)
            {
                double dis = p_[i].dis(p_[j]);
                q.push(Edge{dis, i, j});
            }
        double ans = 0;
        while(!q.empty())
        {
            Edge e = q.top(); q.pop();
            if(Find(e.u) == Find(e.v))
                continue;
            ans = max(ans, e.dis);
            Merge(e.u, e.v);
        }
        print("%.10lf", ans);
    }
};



struct Edge {
    double dis;
    int u, v;
}
bool cmp(const Edge& A, const Edge& B)
{
    return A.dis > B.dis;
}
void Test()
{
    freopen("temp\\in.txt", "r", stdin);
}
int main()
{
    // Test();
    int n;
    cin >> n;
    Polygon G;
    G.Input(n);
    G.Calc();

    return 0;
}