计算几何 get ！
虽然还没 get 但很快就要 get 了。
找了一篇很好的文章仔细看一下，很快就要开计算几何的坑了！
2018-10-14 20:20
2018-10-15 15:15
没错我说到做到，从来不咕咕乱叫。
这么快就开新坑的原因是刚刚一遍切蓝非常的爽，而且这个时间也非常有纪念意义（三 15）
模拟：
传送门
这道题一拿来没反应过来是计算几何，这不是一道大模拟吗？（其实也不算大） 直到发现要求矩形的顶点坐标时才用到了一点向量的知识，判垂直不多解释。
基本上没什么难点，就是码力问题，
代码有些冗余，可能显得很蠢，不过我可以对齐！
没错，对齐怪登场！
#define MAXN 105
#define FUXN 400*400
#define PII pair<double,int>
int T,s,t,A,B,tot,cnt;
double ans;
int st[5],ed[5];
int head[FUXN],vis[MAXN];
double dis[MAXN];
priority_queue<PII,vector<PII>,greater<PII> >que;
struct node{
int to,next;
double w;
void Cln(void) {to = next = w = 0;}
}map[2*FUXN];
void add(int u, int v, double w){
map[++cnt] = (node){v,head[u],w};
head[u] = cnt;
}
struct mat{ // 1 - 3, 2 - 4
double x[5];
double y[5];
int point_num[5];
double city_train;
void f__k(double xa,double ya,double xb,double yb,double xc,double yc,double val)
{
x[1] = xa; y[1] = ya;
x[2] = xb; y[2] = yb;
x[4] = xc; y[4] = yc;
x[3] = x[2]-x[1]+x[4];
y[3] = y[2]-y[1]+y[4];
for(int i=1;i<=4;i++) point_num[i] = ++tot;
city_train = val;
}
void cln(void){
for(int i=0;i<=5;i++) x[i] = y[i] = point_num[i] = 0;
city_train = 0;
}
}city[MAXN];
bool find_90(double midx,double midy,double x1,double y1,double x2,double y2)
{
double t1x,t1y,t2x,t2y;
t1x = x1-midx; t1y = y1-midy;
t2x = x2-midx; t2y = y2-midy;
if(t1x*t2x+t1y*t2y == 0) return 1;
return 0;
}
double dist(double x1, double y1, double x2, double y2){
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
void heap_Dijkstra(int s)
{
for(int i=1;i<=tot;++i) dis[i] = 1061109567;
memset(vis,0 ,sizeof vis);
que.push(make_pair(0,s));
dis[s] = 0;
while(!que.empty())
{
int u = que.top().second;
que.pop();
if(vis[u]) continue;
vis[u] = 1;
for(int k=head[u];k;k=map[k].next)
{
int v = map[k].to;
double w = map[k].w;
if( dis[v] > dis[u]+w)
{
dis[v] = dis[u]+w;
que.push(make_pair(dis[v],v));
}
}
}
}
void init(void)
{
memset(head,0,sizeof head);
memset(st ,0,sizeof st );
memset(ed ,0,sizeof ed );
ans = 1061109567;
tot = cnt = 0;
for(int i=1;i<=MAXN;i++) city[i].cln(),map[i].Cln();
}
int main(void)
{
cin >> T;
while(T--)
{
init();
cin >> s >> t >> A >> B;
for(int i=1;i<=s;i++)
{
double x1,y1,x2,y2,x3,y3,Ti;
cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> Ti;
if(find_90(x2,y2,x1,y1,x3,y3)) city[i].f__k(x2,y2,x1,y1,x3,y3,Ti);else
if(find_90(x1,y1,x2,y2,x3,y3)) city[i].f__k(x1,y1,x2,y2,x3,y3,Ti);else
if(find_90(x3,y3,x1,y1,x2,y2)) city[i].f__k(x3,y3,x1,y1,x2,y2,Ti);
}
for(int i=1;i<=s;i++)
{
for(int j=i+1;j<=s;j++)
for(int p1=1;p1<=4;p1++)
for(int p2=1;p2<=4;p2++)
{
int u = city[i].point_num[p1];
int v = city[j].point_num[p2];
double x1 = city[i].x[p1],y1 = city[i].y[p1];
double x2 = city[j].x[p2],y2 = city[j].y[p2];
double w = dist(x1,y1,x2,y2)*t;
add(u,v,w); add(v,u,w);
}
for(int p1= 1;p1<=4;p1++)
for(int p2=p1+1;p2<=4;p2++)
{
int u = city[i].point_num[p1];
int v = city[i].point_num[p2];
double x1 = city[i].x[p1],y1 = city[i].y[p1];
double x2 = city[i].x[p2],y2 = city[i].y[p2];
double w = dist(x1,y1,x2,y2)*city[i].city_train;
add(u,v,w); add(v,u,w);
}
if(i == A)
for(int p1=1;p1<=4;p1++) st[p1] = city[i].point_num[p1];
if(i == B)
for(int p1=1;p1<=4;p1++) ed[p1] = city[i].point_num[p1];
}
for(int i=1;i<=4;i++)
{
heap_Dijkstra(st[i]);
for(int j=1;j<=4;j++)
ans = min(ans,dis[ed[j]]);
}
printf("%.1lf",ans);
}
return 0;
}