---
url: /algo/zs7tptx5/index.md
---
## Preface

首先介绍一下 DAG，叫做有向无环图，英文名叫 Directed Acyclic Graph，缩写是 DAG。如果你想了解更详细的内容可以前往 [OI-WIKI](https://oi-wiki.org/graph/dag/)

如下图所示，就是一个 DAG，因为它没有环路。

那么这个博客的灵感就来源于我最近做的一个 [F. Parabola Independence](https://codeforces.com/problemset/problem/2195/F)，先来简单讲一下题目意思：

## 题目

给定 $n$ 个形如 $g:g(x)=ax^2+bx+c,x\in \mathbb{R}$ 的双曲线，如果称 $g\_1,g\_2$ 是独立的，当且仅当它们在坐标系上没有交点。

如果称一个有序函数集合 $G={g\_1,g\_2,g\_3,\cdots,g\_n}$ 是 `organized` 的，当且仅当 $\forall ~ i,j,1\leqslant i\<j\leqslant |G|$ 都满足 $g\_i,g\_j$ 是独立的。

现有一个集合 $F={f\_1,f\_2,f\_3,\cdots,f\_n}$ 求 $\forall ~i=1,2,3,\cdots,n$，计算包含其 `organized` 的最大子集大小。如下图所示，橙色与红色不满足独立，但蓝色满足与红色独立，且与橙色也独立。

数据范围满足 $n\leqslant 3000,a,b,c\leqslant 1\times 10^9$

## 分析问题

首先我们先判定两个函数 $f,g$ 是否独立，我们可以通过 $f-g$ 的判别式进行判断，设两个函数分别为：

1. $f(x) = a\_1x^2 + b\_1x + c\_1$
2. $g(x) = a\_2x^2 + b\_2x + c\_2$

则

$$
f-g\Longrightarrow (a\_1 - a\_2)x^2 + (b\_1 - b\_2)x + (c\_1 - c\_2) = 0
$$

计算判别式 $\Delta = B^2 - 4AC$，若 $\Delta \geqslant 0$，则有交点，下面是实现方案：

```cpp :title="hasIntersection.cc" :collapsed-lines
bool hasIntersection(int a1, int b1, int c1, int a2, int b2, int c2)
{

    ll A = (ll)a1 - a2;
    ll B = (ll)b1 - b2;
    ll C = (ll)c1 - c2;

    if (A != 0)
    {

        ll delta = B * B - 4 * A * C;
        return delta >= 0;
    }
    else
    {

        if (B != 0)
        {

            return true;
        }
        else
        {

            return C == 0;
        }
    }
}
```

然后我们注意数据范围是 $n\leqslant 3000$，那么期望复杂度是 $O(n^2)$