Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cmath>
- using namespace std;
- // Define a structure to represent a point
- struct Point {
- double x, y;
- };
- // Calculate the cross product of two vectors
- double crossProduct(Point a, Point b, Point c) {
- return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
- }
- // Check if two points are on the same side of a line passing through two other points
- bool sameSide(Point a, Point b, Point c, Point d) {
- double cp1 = crossProduct(c, d, a);
- double cp2 = crossProduct(c, d, b);
- return cp1 * cp2 >= 0;
- }
- // Check if there exists a point that all the other thirteen points lie on the same side of the line passing through these points
- bool hasSameSidePoint(Point points[], int n) {
- for (int i = 0; i < n; i++) {
- int count1 = 0, count2 = 0;
- for (int j = 0; j < n; j++) {
- if (i != j) {
- if (sameSide(points[i], points[j], points[i+1], points[(i+2)%n])) {
- count1++;
- }
- if (sameSide(points[i], points[j], points[i+1], points[(i+n-1)%n])) {
- count2++;
- }
- }
- }
- if (count1 == n-2 || count2 == n-2) {
- return true;
- }
- }
- return false;
- }
- int main() {
- // Define the set of points
- Point points[15] = {{0, 0}, {1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {6, 6}, {7, 7}, {8, 8}, {9, 9}, {10, 10}, {11, 11}, {12, 12}, {13, 13}, {14, 14}};
- int n = 15;
- // Check if there exists a point that all the other thirteen points lie on the same side of the line passing through these points
- bool result = hasSameSidePoint(points, n);
- // Output the result
- if (result) {
- cout << "There exists a point that all the other thirteen points lie on the same side of the line passing through these points." << endl;
- } else {
- cout << "There does not exist a point that all the other thirteen points lie on the same side of the line passing through these points." << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement