專門做電容的網(wǎng)站有哪些實(shí)用的網(wǎng)絡(luò)推廣方法
凸包
描述
給定n個(gè)二維平面上的點(diǎn)，求他們的凸包。
輸入
第一行包含一個(gè)正整數(shù)n。
接下來n行，每行包含兩個(gè)整數(shù)x,y，表示一個(gè)點(diǎn)的坐標(biāo)。
輸出
令所有在凸包極邊上的點(diǎn)依次為p1,p2,...,pm（序號(hào)），其中m表示點(diǎn)的個(gè)數(shù)，請(qǐng)輸出以下整數(shù)：
(p1 × p2 × ... × pm × m) mod (n + 1)
樣例1輸入
10
7 9
-8 -1
-3 -1
1 4
-3 9
6 -4
7 5
6 6
-6 10
0 8
樣例1輸出
7
樣例1解釋
所以答案為(9 × 2 × 6 × 7 × 1 × 5) % (10 + 1) = 7
樣例2
請(qǐng)查看下發(fā)文件內(nèi)的sample2_input.txt和sample2_output.txt。
限制
3 ≤ n ≤ 10^5
所有點(diǎn)的坐標(biāo)均為范圍(-10^5, 10^5)內(nèi)的整數(shù)，且沒有重合點(diǎn)。每個(gè)點(diǎn)在(-10^5, 10^5) × (-10^5, 10^5)范圍內(nèi)均勻隨機(jī)選取
極邊上的所有點(diǎn)均被視作極點(diǎn)，故在輸出時(shí)亦不得遺漏
時(shí)間：4 sec
空間：512 MB
代碼實(shí)現(xiàn)?
from typing import List, Tupleclass Ip:def __init__(self, x:int = 0, y:int = 0, i:int = 0) -> None:self.x = xself.y = yself.i = idef __sub__(self, other: 'Ip') -> 'Ip':return Ip(self.x - other.x, self.y - other.y)@classmethoddef read(cls, index: int) -> 'Ip':x, y = map(int, input().strip().split())return cls(x, y, index)def cross_product(a: Ip, b: Ip) -> int:return a.x * b.y - a.y * b.xdef convex(a: List[Ip]) -> List[Ip]:a.sort(key=lambda p: (p.x, p.y))b = []for p in a:while len(b) > 1:if cross_product(b[-1] - b[-2], p - b[-2]) <= 0:breakb.pop()b.append(p)temp = b[:]for p in reversed(a[:-1]):while len(b) > len(temp):if cross_product(b[-1] - b[-2], p - b[-2]) <= 0:breakb.pop()b.append(p)return b[:-1]if __name__ == "__main__":n = int(input().strip())a = [Ip.read(i + 1) for i in range(n)]b = convex(a)ans = len(b)for p in b:ans = (ans * p.i) % (n + 1)print(ans)圖
描述
一個(gè)數(shù)列 a 稱為合法的當(dāng)且僅對(duì)于所有的位置 i, j（i < j ≤ n），都不存在一條從 aj 點(diǎn)連向 ai 的有向邊?，F(xiàn)在有很多個(gè)有向無環(huán)圖，請(qǐng)你判斷每個(gè)圖是否只存在唯一的合法數(shù)列。
輸入
輸入的第一行包含一個(gè)正整數(shù) T ，表示數(shù)據(jù)組數(shù)。
對(duì)于每組數(shù)據(jù)，第一行包含兩個(gè)正整數(shù) n, m，表示圖的節(jié)點(diǎn)個(gè)數(shù)和邊數(shù)。
接下來 m 行，每行包含兩個(gè)正整數(shù) x, y（x, y ≤ n），表示這個(gè)圖有一條從 x 到 y 的有向邊。
保證沒有自環(huán)和重邊。
輸出
輸出 T 行，若所給的圖存在唯一的合法數(shù)列，輸出 1，否則輸出 0。
樣例1輸入
2
3 2
1 2
2 3
3 2
1 2
1 3
樣例1輸出
1
0
樣例1解釋
第一個(gè)圖只有一個(gè)合法數(shù)列：1、2、3；
第二個(gè)圖有兩個(gè)合法數(shù)列：1、2、3 或者 1、3、2。
樣例2
請(qǐng)查看下發(fā)文件內(nèi)的sample2_input.txt和sample2_output.txt。
限制
對(duì)于50%的數(shù)據(jù)，n, m ≤ 100；
對(duì)于100%的數(shù)據(jù)，T ≤ 100, n, m ≤ 10000。
時(shí)間：4 sec
空間：512 MB
提示
[本題就是判斷一個(gè)有向無環(huán)圖是否存在唯一的拓?fù)湫蛄?。]
[回憶一下求拓?fù)湫蛄惺侨绾巫龅?#xff1a;每一次都取一個(gè)入度為0的點(diǎn)，將這個(gè)點(diǎn)取出來放進(jìn)拓?fù)湫蛄欣?#xff0c;然后將這個(gè)點(diǎn)連向的所有點(diǎn)的入度減去1。]
[可以發(fā)現(xiàn)，在“每一次都取一個(gè)入度為0”這一步，若入度為0的點(diǎn)數(shù)多于1個(gè)，則顯然拓?fù)湫虿晃ㄒ?。]
[因此按照這個(gè)拓?fù)湫蛩惴ㄗ鲆槐榫秃谩
代碼實(shí)現(xiàn)?
from collections import dequedef has_unique_topological_order(n, m, edges):in_degrees = [0] * (n + 1)adj_list = [[] for _ in range(n + 1)]for x, y in edges:in_degrees[y] += 1adj_list[x].append(y)zero_degree_queue = deque()for i in range(1, n + 1):if in_degrees[i] == 0:zero_degree_queue.append(i)count = 0while zero_degree_queue:if len(zero_degree_queue) > 1:return 0node = zero_degree_queue.popleft()count += 1for neighbor in adj_list[node]:in_degrees[neighbor] -= 1if in_degrees[neighbor] == 0:zero_degree_queue.append(neighbor)return 1 if count == n else 0def main():T = int(input())for _ in range(T):n, m = map(int, input().split())edges = [tuple(map(int, input().split())) for _ in range(m)]print(has_unique_topological_order(n, m, edges))if __name__ == "__main__":main()