 |
|
 |
|
|
|
http://acm.hdu.edu.cn/showproblem.php?pid=2355
The Sidewinder Sleeps
直线反射
//http://acm.hdu.edu.cn/showproblem.php?pid=2353
//http://www.geometryalgorithms.com/Archive/algorithm_0104/algorithm_0104B.htm
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
using namespace std;
const double inf = 1e15;
const double eps = 1e-6;
const double pi = acos(-1.0);
int P;
int ans[100005];
int ansl;
struct TPoint
{
double x, y;
};
struct TSeg
{
char MSD;
TPoint start, end;
}seg[105];
struct TLine
{
double a, b, c;
}line[105];
double max(double x, double y)
{
if(x > y) return x;
else return y;
}
double min(double x, double y)
{
if(x < y) return x;
else return y;
}
double multi(TPoint p1, TPoint p2, TPoint p0)
{
return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}
int isIntersected(TPoint s1, TPoint e1, TPoint s2, TPoint e2)
{
if(
(max(s1.x, e1.x) >= min(s2.x, e2.x)) &&
(max(s2.x, e2.x) >= min(s1.x, e1.x)) &&
(max(s1.y, e1.y) >= min(s2.y, e2.y)) &&
(max(s2.y, e2.y) >= min(s1.y, e1.y)) &&
(multi(s2, e1, s1) * multi(e1, e2, s1) >= 0) &&
(multi(s1, e2, s2) * multi(e2, e1, s2) >= 0)
) return 1;
return 0;
}
TPoint LineInter(TLine l1, TLine l2)
{
TPoint tmp;
double a1 = l1.a;
double b1 = l1.b;
double c1 = l1.c;
double a2 = l2.a;
double b2 = l2.b;
double c2 = l2.c;
if(fabs(b1) < eps){
tmp.x = -c1 / a1;
tmp.y = (-c2 - a2 * tmp.x) / b2;
}
else{
tmp.x = (c1 * b2 - b1 * c2) / (b1 * a2 - b2 * a1);
tmp.y = (-c1 - a1 * tmp.x) / b1;
}
return tmp;
}
TLine lineFromSegment(TPoint p1, TPoint p2)
{
TLine tmp;
tmp.a = p2.y - p1.y;
tmp.b = p1.x - p2.x;
tmp.c = p2.x * p1.y - p1.x * p2.y;
return tmp;
}
TPoint symmetricalPointofLine(TPoint p, TLine L)
{
TPoint p2;
double d;
d = L.a * L.a + L.b * L.b;
p2.x = (L.b * L.b * p.x - L.a * L.a * p.x -
2 * L.a * L.b * p.y - 2 * L.a * L.c) / d;
p2.y = (L.a * L.a * p.y - L.b * L.b * p.y -
2 * L.a * L.b * p.x - 2 * L.b * L.c) / d;
return p2;
}
double dis(TPoint p1, TPoint p2)
{
return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
TLine SloveLine(TPoint start, TPoint dir)
{
TLine line;
if(dir.x == 0)
{
line.a = 1;
line.b = 0;
line.c = -start.x;
}
else
