## 【POJ-1269】Intersecting Lines【直线位置判断】

【POJ-1269】Intersecting Lines【直线位置判断】

Solution:

```#include <iostream>

using namespace std;

struct Point {
int x, y;
Point operator - (Point b) {
Point ret = {x - b.x, y - b.y};
return ret;
}
bool operator == (const Point &p) {return x == p.x && y == p.y;}
int cross(Point v) {
return x * v.y - y * v.x;
}
};
inline int maxi(int a, int b) {return a > b ? a : b;}
inline int mini(int a, int b) {return a < b ? a : b;}
enum {COUNT, CLOCK, COL};
int getOrientation(Point a, Point b, Point c) {
Point vab = b - a;      /* The vector of a -> b */
Point vac = c - a;      /* The vector of a -> c */
int crossPro = vab.cross(vac);
if (crossPro < 0) return CLOCK;
if (crossPro > 0) return COUNT;
return COL;
}

enum {POINT, NONE, LINE};
int isIntersect(Point ps1, Point pe1, Point ps2, Point pe2) {
int oa = getOrientation(ps1, ps2, pe1);
int ob = getOrientation(ps1, pe2, pe1);
if (oa == COL && ob == COL) return LINE;
Point v = pe1 - ps1;
Point v2 = pe2 - ps2;
if (!v.cross(v2)) return NONE;
return POINT;
}
double ans[2];
void setAns(const Point &p) {
ans[0] = p.x;
ans[1] = p.y;
}
void getInterPoint(Point ps1, Point pe1, Point ps2, Point pe2) {
if (ps1 == ps2 || ps1 == pe2) setAns(ps1);
if (pe1 == ps2 || pe1 == pe2) setAns(pe1);
double k1 = (pe1.y - ps1.y) * 1.0 / (pe1.x - ps1.x);
double b1 = ps1.y - ps1.x * k1;
double k2 = (pe2.y - ps2.y) * 1.0 / (pe2.x - ps2.x);
double b2 = ps2.y - ps2.x * k2;
if (ps1.x == pe1.x) {
ans[0] = ps1.x;
ans[1] = k2 * ans[0] + b2;
} else if (ps2.x == pe2.x) {
ans[0] = ps2.x;
ans[1] = k1 * ans[0] + b1;
} else {
ans[0] = (b2 - b1) / (k1 - k2);
ans[1] = k1 * ans[0] + b1;
}
}

int main(void) {
int n;
Point ps1, pe1, ps2, pe2;
while (~scanf("%d", &n)) {
printf("INTERSECTING LINES OUTPUT\n");
while (n--) {
scanf("%d%d%d%d%d%d%d%d", &ps1.x, &ps1.y, &pe1.x, &pe1.y,
&ps2.x, &ps2.y, &pe2.x, &pe2.y);
if (ps1 == pe1 || ps2 == pe2) {
printf("NONE\n");
continue;
}
int state = isIntersect(ps1, pe1, ps2, pe2);
if (state == LINE) printf("LINE\n");
else if (state == NONE) printf("NONE\n");
else {
getInterPoint(ps1, pe1, ps2, pe2);
printf("POINT %.2f %.2f\n", ans[0], ans[1]);
}
}
printf("END OF OUTPUT\n");
}
return 0;
}
```