本文主要是介绍2014 Multi-University Training Contest 8小记，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1002 计算几何
最大的速度才可能拥有无限的面积。
最大的速度的点 求凸包， 凸包上的点（ 注意不是端点 ） 才拥有无限的面积
注意 ： 凸包上如果有重点则不满足。
另外最大的速度为0也不行的。
int cmp(double x){if(fabs(x) < 1e-8) return 0 ;if(x > 0) return 1 ;return -1 ;
}struct point{int x , y ;point(){}point(int _x , int _y):x(_x) , y(_y){}friend bool operator == (const point &a , const point &b){return cmp(a.x - b.x) == 0 && cmp(a.y - b.y) == 0 ;}friend double operator ^ (const point &a , const point &b){return a.x * b.y - a.y * b.x ;}point operator - (point o){return point(x - o.x , y - o.y) ;}
};struct Poly{vector<point> p ;Poly(){}Poly(int s = 0){p.resize(s) ;}
} ;bool cmpless(const point &a , const point &b){return cmp(a.x - b.x) < 0|| cmp(a.x - b.x == 0) && cmp(a.y - b.y) < 0 ;
}Poly convex_hull(vector<point> a){Poly src(2 * a.size() + 5) ;sort(a.begin() , a.end() , cmpless) ;a.erase(unique(a.begin() , a.end()) , a.end()) ;int m = 0 ;for(int i = 0 ; i < a.size() ; i++){while(m > 1 && cmp( (src.p[m-1] - src.p[m-2]) ^ (a[i] - src.p[m-2]) ) <= 0)m-- ;src.p[m++] = a[i] ;}int k = m ;for(int i = a.size() - 2 ; i >= 0 ; i--){while(m > k && cmp( (src.p[m-1] - src.p[m-2]) ^ (a[i] - src.p[m-2])) <= 0)m-- ;src.p[m++] = a[i] ;}src.p.resize(m) ;if(a.size() > 1) src.p.resize(m-1) ;return src ;
}struct node{point a ;int v ;int id ;int recover ;
}man[508] ;int answer[508] ;int main(){int n , T = 1 , mxv , i , j ;while(cin>>n && n){mxv = -1 ;for(i = 0 ; i < n ; i++){scanf("%d%d%d" , &man[i].a.x , &man[i].a.y , &man[i].v) ;man[i].id = i ;mxv = max(mxv , man[i].v) ;}printf("Case #%d: " , T++) ;if(mxv == 0){for(i = 0 ; i < n ; i++) putchar('0') ;puts("") ;continue ;}for(i = 0 ; i < n ; i++) man[i].recover = 0 ;for(i = 0 ; i < n ; i++){if(man[i].v != mxv) continue ;for(j = i+1 ; j < n ; j++){if(man[i].v == man[j].v && man[i].a == man[j].a){man[i].recover = man[j].recover = 1 ;}}}vector<node> Man ; vector<point> lis ; for(i = 0 ; i < n ; i++){if(man[i].v == mxv){Man.push_back(man[i]) ;lis.push_back(man[i].a) ;}}Poly po = convex_hull(lis) ;memset(answer , 0 , sizeof(answer)) ;for(i = 0 ; i < Man.size() ; i++){node now = Man[i] ;if(now.recover == 1) continue ;for(j = 0 ; j < po.p.size() ; j++){if(cmp( (now.a-po.p[j]) ^ (now.a - po.p[(j+1)%po.p.size()] ) ) == 0){answer[now.id] = 1 ;break ;}}}for(i = 0 ; i < n ; i++) printf("%d" , answer[i]) ;puts("") ;}return 0 ;
}1006 贪心
typedef long long LL ;LL h , a , b , k ;int ok(){if(h - a < 1) return 1 ;if(h - k * a + (k-1) * b < 1 ) return 1 ;if(- k * a + (k+1) * b < 0) return 1 ;return 0 ;
}int main(){int T = 1 ;while(cin>>h>>a>>b>>k){if(h == 0 && a==0 && b==0 && k==0 ) break ;printf("Case #%d: " , T++) ;if(ok()) puts("YES") ;else puts("NO") ;}return 0 ;
}1008 找规律
typedef long long LL ;LL a , k ;int main(){LL i , A , n , t , pt , T = 1 ;while(cin>>a>>k){if(a == 0 && k == 0) break ; A = a ;pt = -1 ;for(i = 1 ; i <= k ; i++){if(A % i == 0) t = A / i ;else {A = ((A / i) + 1 ) * i ;t = A / i ;}if(t == pt) break ;pt = t ;}printf("Case #%d: " , T++) ;cout<< t * k << endl ;}return 0 ;
}
这篇关于2014 Multi-University Training Contest 8小记的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
