题目链接：P1919 【模板】A*B Problem升级版（FFT快速傅里叶）
题意
给定两个 $n$ 位 $10$ 进制整数 $x$ 和 $y$，求 $x*y$。
2019 ACM-ICPC 上海网络赛 B. Light bulbs (差分)
题目链接：Light bulbs
比赛链接：The Preliminary Contest for ICPC Asia Shanghai 2019
题意
给定 $N$ 个灯泡 (编号从 $0$ 到 $N - 1$)，初始都是关闭的。
给定 $M$ 个操作，每个操作包含 $L$ 和 $R$，对 $[L, R]$ 内的所有灯泡改变状态。
求最后有几个灯泡是亮的。
POJ 1474 Video Surveillance (半平面交)
题目链接：POJ 1474
Description
A friend of yours has taken the job of security officer at the Star-Buy Company, a famous depart- ment store. One of his tasks is to install a video surveillance system to guarantee the security of the customers (and the security of the merchandise of course) on all of the store’s countless floors. As the company has only a limited budget, there will be only one camera on every floor. But these cameras may turn around to look in every direction.
The first problem is to choose where to install the camera for every floor. The only requirement is that every part of the room must be visible from there. In the following figure the left floor can be completely surveyed from the position indicated by a dot, while for the right floor, there is no such position, the given position failing to see the lower left part of the floor.
Before trying to install the cameras, your friend first wants to know whether there is indeed a suitable position for them. He therefore asks you to write a program that, given a ground plan, de- termines whether there is a position from which the whole floor is visible. All floor ground plans form rectangular polygons, whose edges do not intersect each other and touch each other only at the corners.
HDU 5119 Happy Matt Friends (背包DP + 滚动数组)
题目链接：HDU 5119
Problem Description
Matt has N friends. They are playing a game together.
Each of Matt’s friends has a magic number. In the game, Matt selects some (could be zero) of his friends. If the xor (exclusive-or) sum of the selected friends’magic numbers is no less than M , Matt wins.
Matt wants to know the number of ways to win.
洛谷 P1613 跑路 (倍增 + DP + 最短路)
POJ 3130 How I Mathematician Wonder What You Are! (半平面交)
题目链接：POJ 3130
Problem Description
After counting so many stars in the sky in his childhood, Isaac, now an astronomer and a mathematician uses a big astronomical telescope and lets his image processing program count stars. The hardest part of the program is to judge if shining object in the sky is really a star. As a mathematician, the only way he knows is to apply a mathematical definition of stars.
The mathematical definition of a star shape is as follows: A planar shape $F$ is star-shaped if and only if there is a point $C \in F$ such that, for any point $P \in F$, the line segment $CP$ is contained in $F$. Such a point $C$ is called a center of $F$. To get accustomed to the definition let’s see some examples below.
The first two are what you would normally call stars. According to the above definition, however, all shapes in the first row are star-shaped. The two in the second row are not. For each star shape, a center is indicated with a dot. Note that a star shape in general has infinitely many centers. Fore Example, for the third quadrangular shape, all points in it are centers.
Your job is to write a program that tells whether a given polygonal shape is star-shaped or not.
POJ 1279 Art Gallery (半平面交)
题目链接：POJ 1279
Problem Description
The art galleries of the new and very futuristic building of the Center for Balkan Cooperation have the form of polygons (not necessarily convex). When a big exhibition is organized, watching over all of the pictures is a big security concern. Your task is that for a given gallery to write a program which finds the surface of the area of the floor, from which each point on the walls of the gallery is visible. On the figure 1. a map of a gallery is given in some co-ordinate system. The area wanted is shaded on the figure 2.
POJ 2451 Uyuw's Concert (半平面交)
题目链接：POJ 2451
Problem Description
Prince Remmarguts solved the CHESS puzzle successfully. As an award, Uyuw planned to hold a concert in a huge piazza named after its great designer Ihsnayish.
The piazza in UDF - United Delta of Freedom’s downtown was a square of [0, 10000] * [0, 10000]. Some basket chairs had been standing there for years, but in a terrible mess. Look at the following graph.
In this case we have three chairs, and the audiences face the direction as what arrows have pointed out. The chairs were old-aged and too heavy to be moved. Princess Remmarguts told the piazza’s current owner Mr. UW, to build a large stage inside it. The stage must be as large as possible, but he should also make sure the audience in every position of every chair would be able to see the stage without turning aside (that means the stage is in the forward direction of their own).
To make it simple, the stage could be set highly enough to make sure even thousands of chairs were in front of you, as long as you were facing the stage, you would be able to see the singer / pianist – Uyuw.
Being a mad idolater, can you tell them the maximal size of the stage?
