生活随笔
收集整理的這篇文章主要介紹了
Mr. Main and Windmills 模拟，计算几何（昆明）
小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
- O(nmlogn)O(nmlogn)O(nmlogn)，這么一算都1e8了
- long double，但好像double也可以過(guò)
#include
<iostream
>
#include
<algorithm
>
#include
<cstring
>
#include
<queue
>
#include
<vector
>
#define
debug(a
) cout
<< #a
<< " = " << a
<< endl
;
#define LD long double
using namespace std
;
typedef long long ll
;const int N
= 1005;
const double INF
= 1e9 + 7;struct point
{LD x
, y
;
}A
[N
], stk
[N
];LD
slope(point s
, point t
)
{if (s
.x
== t
.x
)return INF
;return (t
.y
- s
.y
) / (t
.x
- s
.x
);
}struct line
{LD k
, b
;point fromP
, endP
;line(){}line(point s
, point t
){fromP
= s
, endP
= t
;k
= slope(s
, t
);if (k
== INF
) b
= INF
;else b
= s
.y
- k
* s
.x
;}
};point
findPoint(line a
, line b
)
{if (a
.k
== b
.k
)return point
{INF
, INF
};LD xpos
, ypos
;if (a
.k
== INF
)xpos
= a
.fromP
.x
;else if (b
.k
== INF
)xpos
= b
.fromP
.x
;elsexpos
= (b
.b
- a
.b
) / (a
.k
- b
.k
);if (a
.k
== 0)ypos
= a
.fromP
.y
;else if (b
.k
== 0)ypos
= b
.fromP
.y
;elseypos
= xpos
* a
.k
+ a
.b
;return point
{xpos
, ypos
};
}int getAllPoint(int n
, int h
, line city
)
{int cnt
= 0;point s
= city
.fromP
, t
= city
.endP
;for (int i
= 1; i
<= n
; i
++ ){if (i
== h
) continue;line now
= line(A
[i
], A
[h
]);if (now
.k
== city
.k
)continue;point get
= findPoint(now
, city
);if (get
.x
< min(s
.x
, t
.x
) || get
.x
> max(s
.x
, t
.x
) || get
.y
< min(s
.y
, t
.y
) || get
.y
> max(s
.y
, t
.y
))continue;stk
[ ++ cnt
] = get
;}return cnt
;
}int main()
{int n
, m
;scanf("%d%d", &n
, &m
);point s
, t
;scanf("%LF%LF%LF%LF", &s
.x
, &s
.y
, &t
.x
, &t
.y
);line city
= line(s
, t
);for (int i
= 1; i
<= n
; i
++ ){scanf("%LF%LF", &A
[i
].x
, &A
[i
].y
);}for (int i
= 1; i
<= m
; i
++ ){int h
, k
;scanf("%d%d", &h
, &k
);int len = getAllPoint(n
, h
, city
);if (k
> len){printf("-1\n");}else{if (city
.k
== 0)sort(stk
+ 1, stk
+ 1 + len, [](point a
, point b
){return a
.x
< b
.x
;});elsesort(stk
+ 1, stk
+ 1 + len, [](point a
, point b
){return a
.y
< b
.y
;});if (s
.y
> t
.y
)reverse(stk
+ 1, stk
+ 1 + len);if (city
.k
== 0 && s
.x
> t
.x
)reverse(stk
+ 1, stk
+ 1 + len);printf("%.10LF %.10LF\n", stk
[k
].x
, stk
[k
].y
);}}return 0;
}
總結(jié)
以上是生活随笔為你收集整理的Mr. Main and Windmills 模拟，计算几何（昆明）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
