# CSP 202006-1 线性分类器

 123456789101112131415161718192021222324252627282930313233343536373839404142434445 #include #include #include #include #include #include #include #include using namespace std; int n,m; long long x[1005], y[1005]; char type[1005]; long long theta0,theta1,theta2; bool checkPointPos(long long x,long long y){     return theta0+theta1*x+theta2*y > 0; } bool checkLine(){     char typ = type[0];     bool pos = checkPointPos(x[0], y[0]);     for(int i=1;i>n>>m;     for(int i=0;i>x[i]>>y[i]>>type[i];     for(int i=0;i>theta0>>theta1>>theta2;         if(checkLine()){             cout<<"Yes\n";         }else{             cout<<"No\n";         }     } }

# 洛谷 P2742 [USACO5.1]圈奶牛Fencing the Cows /【模板】二维凸包

 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283 #include #include #include #include #include #include using namespace std; struct point {     double x, y;     long long id;     point() :x(0), y(0) {}     bool operator ==(const point& p) const {         return x == p.x && y == p.y;     } }PP; //PP: Polar Point vector points; double area2(point p, point q, point s) {     /*     |p.x p.y 1|     |q.x q.y 1| == 2*DirectedTriangleArea(p,q,s)     |s.x s.y 1|     */     return p.x * q.y - s.x * q.y         + q.x * s.y - q.x * p.y         + s.x * p.y - p.x * s.y; } bool toLeftTest(point p, point q, point s) {     //When return value large than 0, S is on the left side of ray PQ     return area2(p, q, s) > 0; } bool toLeftTest2(point p, point q, point s) {     //When return value large than 0, S is on the left side of ray PQ     return area2(p, q, s) >= 0; } bool cmp(const point& p1, const point& p2) { // Sort according to polar angle     return PP == p1 || !(PP == p2) && toLeftTest(PP, p1, p2); } point LTL(vector& points) { //Lowest then leftmost     point ltl = points[0];     for (int i = 1; i < points.size(); i++) {         if (points[i].y < ltl.y || points[i].y == ltl.y && points[i].x < ltl.x)             ltl = points[i];     }     return ltl; } vector grahamScan() {     PP = LTL(points);     sort(points.begin(), points.end(), cmp);     vector S, T;     S.push_back(points[0]); S.push_back(points[1]);     for (int i = points.size() - 1; i > 1; i--)T.push_back(points[i]);     while (!T.empty()) {         if (toLeftTest2(S[S.size() - 2], S[S.size() - 1], T[T.size() - 1])) {             S.push_back(T[T.size() - 1]);             T.pop_back();         }         else S.pop_back();     }     return S; } double dist(point x, point y) {     return sqrt((x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y)); } int main() {     ios::sync_with_stdio(false);     long long n;     cin >> n;     for (int i = 1; i <= n; i++) {         point tmp;         cin >> tmp.x >> tmp.y;         tmp.id = i;         points.push_back(tmp);     }     vector result;     if (points.size() > 2)result = grahamScan();     else result = points;     double res = 0;     for (int i = 0; i < result.size(); i++) {         res += dist(result[i % result.size()], result[(i + 1) % result.size()]);     }     cout.setf(ios::fixed);     cout << setprecision(2) << res; }

# CG2017 PA1-1 Convex Hull (凸包)

### Description (描述)

After learning Chapter 1, you must have mastered the convex hull very well. Yes, convex hull is at the kernel of computational geometry and serves as a fundamental geometric structure. That’s why you are asked to implement such an algorithm as your first programming assignments.

Specifically, given a set of points in the plane, please construct the convex hull and output an encoded description of all the extreme points.

### Input (输入)

The first line is an integer n > 0, i.e., the total number of input points.

The k-th of the following n lines gives the k-th point:

pk = (xk, yk), k = 1, 2, …, n

Both xk and yk here are integers and they are delimited by a space.

pk = (xk, yk), k = 1, 2, …, n

### Output (输出)

Let { s1, s2, …, sh } be the indices of all the extreme points, h ≤ n. Output the following integer as your solution:

( s1 * s2 * s3 * … * sh * h ) mod (n + 1)

( s1 * s2 * s3 * … * sh * h ) mod (n + 1)

### Sample Input (输入样例)


10
7 9
-8 -1
-3 -1
1 4
-3 9
6 -4
7 5
6 6
-6 10
0 8


### Sample Output (输出样例)


7   // ( 9 x 2 x 6 x 7 x 1 x 5 ) % (10 + 1)


### Limitation (限制)

• 3 ≤ n ≤ 10^5
• Each coordinate of the points is an integer from (-10^5, 10^5). There are no duplicated points. Each point is selected uniformly randomly in (-10^5, 10^5) x (-10^5, 10^5).
• All points on extreme edges are regarded as extreme points and hence should be included in your solution.
• Time Limit: 2 sec
• Space Limit: 512 MB
• 3 ≤ n ≤ 10^5
• 所有点的坐标均为范围(-10^5, 10^5)内的整数，且没有重合点。每个点在(-10^5, 10^5) x (-10^5, 10^5)范围内均匀随机选取
• 极边上的所有点均被视作极点，故在输出时亦不得遗漏
• 时间限制：2 sec
• 空间限制：512 MB

### Hint (提示)

Use the CH algorithms presented in the lectures.

 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879 #include #include #include #include using namespace std; struct point {     long long x, y, id;     point() :x(0), y(0) {}     point(long long x, long long y) :x(x), y(y) {}     bool operator ==(const point& p) const {         return x == p.x && y == p.y;     } }PP; //PP: Polar Point vector points; long long area2(point p, point q, point s) {     /*     |p.x p.y 1|     |q.x q.y 1| == 2*DirectedTriangleArea(p,q,s)     |s.x s.y 1|     */     return p.x * q.y - s.x * q.y         + q.x * s.y - q.x * p.y         + s.x * p.y - p.x * s.y; } bool toLeftTest(point p, point q, point s) {     //When return value large than 0, S is on the left side of ray PQ     return area2(p, q, s) > 0; } bool toLeftTest2(point p, point q, point s) {     //When return value large than 0, S is on the left side of ray PQ     return area2(p, q, s) >= 0; } bool cmp(const point& p1, const point& p2) { // Sort according to polar angle     return PP == p1 || !(PP == p2) && toLeftTest(PP, p1, p2); } point LTL(vector& points) { //Lowest then leftmost     point ltl = points[0];     for (int i = 1; i < points.size(); i++) {         if (points[i].y < ltl.y || points[i].y == ltl.y && points[i].x < ltl.x)             ltl = points[i];     }     return ltl; } vector grahamScan() {     PP = LTL(points);     sort(points.begin(), points.end(), cmp);     vector S, T;     S.push_back(points[0]); S.push_back(points[1]);     for (int i = points.size() - 1; i > 1; i--)T.push_back(points[i]);     while (!T.empty()) {         if (toLeftTest2(S[S.size() - 2], S[S.size() - 1], T[T.size() - 1])) {             S.push_back(T[T.size() - 1]);             T.pop_back();         }         else S.pop_back();     }     return S; } int main() {     ios::sync_with_stdio(false);     long long n;     cin >> n;     for (int i = 1; i <= n; i++) {         point tmp;         cin >> tmp.x >> tmp.y;         tmp.id = i;         points.push_back(tmp);     }     vector result;     if (points.size() > 2)result = grahamScan();     else result = points;     long long res = 1;     for (int i = 0; i < result.size(); i++) {         //cout << result[i].id << endl;//debug         res = ((res % (n + 1)) * (result[i].id % (n + 1))) % (n + 1);     }     res = ((res % (n + 1)) * (result.size() % (n + 1))) % (n + 1);     cout << res; }

# 洛谷/USACO 电网 Electric Fences

 1234567891011121314151617181920 #include #include #include #include #include #include #include #include using namespace std; int n, m, p; int gcd(int x, int y){     if (x == 0)return y;     return gcd(y%x, x); } int main(){     ios::sync_with_stdio(false);     cin >> n >> m >> p;     int e = gcd(n, m) + gcd(abs(p - n), m) + p;     printf("%d", p*m/2 + 1 - e / 2); }