http://acm.hdu.edu.cn/showproblem.php?pid=4946

給你n個(gè)點(diǎn)的坐標(biāo)和速度，如果一個(gè)點(diǎn)能夠到達(dá)無(wú)窮遠(yuǎn)處，且花費(fèi)的時(shí)間是最少的，則此點(diǎn)輸出1，否則輸出0.
每個(gè)點(diǎn)向外都是以圓的形式向外拓展的，所以只有速度最大的才能到達(dá)無(wú)窮遠(yuǎn)處，但是并不是所有速度為最大的點(diǎn)都能到到無(wú)窮遠(yuǎn)處。
將速度最大的所有點(diǎn)做一個(gè)凸包，凸包內(nèi)的點(diǎn)肯定不能到達(dá)無(wú)窮遠(yuǎn)處，凸包上的點(diǎn)才滿(mǎn)足條件。

于是找最大速度點(diǎn)構(gòu)成的凸包，標(biāo)記輸出

注意由于有重點(diǎn)的存在，一定要標(biāo)記重點(diǎn)并在求出之后再將其刪去，而不是之前直接判定

#include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <string> #include <queue> #include <vector> #include<set> #include <iostream> #include <algorithm> using namespace std; #define RD(x) scanf("%d",&x) #define RD2(x,y) scanf("%d%d",&x,&y) #define clr0(x) memset(x,0,sizeof(x)) typedef long long LL; const int maxn=10005; struct arr {int x,y,z;int id;bool ans; } a[maxn]; int b[maxn]; bool vis[maxn]; bool cmp(const arr &a, const arr &b) {return (a.x<b.x) || (a.x==b.x && a.y<b.y); }bool cmp_z(const arr &a, const arr &b) {return a.z > b.z; }bool cmp_id(const arr &a, const arr &b) {return a.id < b.id; }int cj(const arr &a, const arr &b, const arr &c) {return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x); }void graham(int n) {int i,m,k;if (n < 1)return ;if (n == 1) {a[0].ans =1;return ;}if (n == 2) {if (a[0].x == a[1].x && a[0].y == a[1].y)return ;a[0].ans = a[1].ans = 1;return ;}sort(a,a+n,cmp);clr0(vis);for (i = 1; i < n; ++i)if (a[i].x == a[i-1].x && a[i].y == a[i-1].y){vis[i] = 1;vis[i - 1]=1;}b[0]=0;b[1]=1;b[2]=2;k=1;for (i=2; i<n; ++i) {while (k && cj(a[i],a[b[k]],a[b[k-1]])>=0) --k;b[++k]=i;}m=k;b[++k]=n-2;for (i=n-3; i>=0; --i) {while (k!=m && cj(a[i],a[b[k]],a[b[k-1]])>=0) --k;b[++k]=i;}m=k;m++;for (i = 0; i < m; ++i)a[b[i]].ans = 1; // for (i = 0; i < m; ++i) // printf("%d %d\n",a[b[i]].x,a[b[i]].y);for (i = 0;i < n;++i)if(a[i].ans == 0)for (int j = 1;j < m;++j)if(cj(a[b[j]],a[b[j-1]],a[i]) == 0){a[i].ans = 1;break;}for (i = 0;i < n;++i)if(vis[i])a[i].ans = 0; }int main() { // freopen("c.in","r",stdin); // freopen("c.txt","w",stdout);int i,n;LL t = 0;while (~RD(n),n) {printf("Case #%I64d: ", ++t);for (i = 0; i < n; ++i) {scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z);a[i].id = i;a[i].ans = 0;}if (n == 1) {if(a[0].z > 0)puts("1");elseputs("0");continue;}sort(a, a + n, cmp_z);if (a[0].z > 0){for (i = 1; i < n; ++i)if (a[i].z != a[0].z) break;graham(i);}sort(a, a + n, cmp_id);for (i = 0; i < n; ++i)if (a[i].ans) putchar('1');else putchar('0');puts("");}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/zibaohun/p/4046831.html

總結(jié)

以上是生活随笔為你收集整理的hdu 4946 凸包注意重点的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。