Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define ll long long
- using namespace std;
- typedef double TT;
- struct point
- {
- int x, y;
- point(){x = y = 0;}
- point(int a, int b){ x = a; y = b; }
- TT operator* (const point &p) const{ // Dot
- return x * p.x + y * p.y;
- }
- TT operator^ (const point &p) const{ // Cross
- return x * p.y - y * p.x;
- }
- 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* (TT scale){
- return point(scale * x, scale * y);
- }
- point operator/ (TT d){
- return point(1.0 * x / d, 1.0 * y / d);
- }
- bool operator< (const point &p) const{
- if (x != p.x) return x < p.x;
- return y < p.y;
- }
- bool operator== (const point &p) const{
- return x == p.x && y == p.y;
- }
- bool operator!= (const point &p) const{
- return !(*this == p);
- }
- void scan(){ scanf("%d%d", &x, &y); }
- double len(){ return hypot(x, y); }
- double dist(const point &p) const{
- return (p - *this).len();
- }
- };
- point rotate(point p, double theta){
- double rad = theta * acos(-1) / 180.0;
- return point(p.x * cos(rad) - p.y * sin(rad),
- p.x * sin(rad) + p.y * cos(rad));
- }
- // Area of triangle
- double AreaOfTri(point a, point b, point c){
- point x = b - a;
- point y = c - a;
- return abs((x ^ y) / 2.0);
- }
- // is three point collinear
- bool Collinear(point a, point b, point c){
- return AreaOfTri(a, b, c) == 0;
- }
- const int Max = 5e5 + 5, Mod = 1e9 + 7;
- point p[Max];
- int n, a[Max], r[Max];
- int LP[Max];
- vector<int> G[Max];
- bool vis[Max], OnStack[Max];
- bool IsCycle(int u)
- {
- if (OnStack[u])
- return 1;
- if (vis[u])
- return 0;
- vis[u] = OnStack[u] = 1;
- for (auto v : G[u])
- if (IsCycle(v))
- return 1;
- OnStack[u] = 0;
- return 0;
- }
- int lp(int u)
- {
- if (LP[u] != -1)
- return LP[u];
- LP[u] = 0;
- for (auto v : G[u])
- LP[u] = max(LP[u], lp(v));
- return LP[u];
- }
- int main()
- {
- ios::sync_with_stdio(0);
- cin.tie(0); cout.tie(0);
- memset(LP, -1, sizeof(LP));
- cin >> n;
- for (int i = 0; i < n; i++){
- p[i].scan();
- cin >> a[i] >> r[i];
- }
- for(int i=0;i<n;i++)
- for(int j=0;j<n;j++){
- point Line = p[i] - p[j];
- point A = rotate(point(1e9, 0), a[j] - r[j]);
- point B = rotate(point(1e9, 0), a[j] + r[j]);
- if( j != i && (A^Line) >= 0 && (Line^B) >= 0)
- G[j].push_back(i);
- }
- for(int i=0;i<n;i++)
- if (!vis[i] && IsCycle(i)){
- cout << -1 << endl;
- return 0;
- }
- for(int i=0;i<n;i++)
- lp(i);
- vector<int> ans[n + 5];
- for (int i = 0; i < n; i++)
- ans[LP[i]].push_back(i);
- for (int i = 0; i <= n; i++)
- for (auto j : ans[i])
- cout << j << ' ';
- cout << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement