Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
竟!然!1!A!附代妈&思路!首先当然是对每个国家求头包,先找到這個国家x值最小的點(如果有多个,找其中y值最小的),這個點一定在头包上。然后对斜率角排序,相同斜率的只保留距离最远的(因为同样斜率距离脚近的點一定在头包内面)。这些“有效顶點”是头包可能的顶點,然后從最小的斜率(其实是找到间隔大于派的两个斜率值,后面的那個就是最小斜率)开始维护头包,每次加入较大斜率的點的时猴,用二分判断当前维护的头包顶点需要保留的部分,并更新。 锝到头包之后只需要逐个三角形地计祘面积,然后的关键就只剩下判断某一个點在不在头包的内面,这个就只需要判断和每一条边的绕向是否一致(或者,张角之和为两倍派,不过這個误差可能会有影响,没试过)。 #include <iostream> #include <stdio.h> #include <algorithm> #include <cmath> using namespace std; const double PI = 3.1415926535; struct pt{ int x,y; double ang; long long int sqrDist; }; bool compare(const pt &p1, const pt &p2){ return p1.ang < p2.ang-1e-8 || (abs(p1.ang-p2.ang)<1e-8 && p1.sqrDist > p2.sqrDist) ; } double cha(double ang1, double ang2){ if(ang1 <= ang2) return ang2 - ang1; return 2*PI - ang1 + ang2; } int sign(pt &p1, pt &p2, pt &p3){ int get = p1.x*p2.y + p2.x*p3.y + p3.x*p1.y - p1.y*p2.x - p2.y*p3.x - p3.y*p1.x; if(get > 0) return 1; else if(get < 0)return -1; else return 0; } bool neimian(pt &p1, pt &p2, pt &p3, pt &origin){ int sign1 = sign(p1, p2, origin); int sign2 = sign(p1, p2, p3); if(sign1 * sign2 == 1) return 0; return 1; } double mianji(pt &p1, pt &p2, pt &p3){ return abs((p1.x*p2.y+p2.x*p3.y+p3.x*p1.y-p1.y*p2.x-p2.y*p3.x-p3.y*p1.x)*0.5); } struct kingdom{ int dianNum; pt points[110]; int toubaoNum; int toubaoIdx[110]; double area; bool getData(); void getToubao(); void getMianji(); }kd[25]; bool kingdom::getData(){ scanf("%d", &dianNum); if(dianNum == -1) return 0; for(int i = 0; i < dianNum; i++){ scanf("%d%d", &points[i].x, &points[i].y); } return 1; } void kingdom::getToubao(){ int mnX = 2147483647, mnY = 2147483647, arg = -1; for(int i = 0; i < dianNum; i++){ if(points[i].x < mnX || (points[i].x == mnX && points[i].y < mnY)){ mnX = points[i].x, mnY = points[i].y; arg = i; } } if(arg != 0){ pt temp = points[0]; points[0] = points[arg]; points[arg] = temp; } for(int i = 1; i < dianNum; i++){ points[i].ang = atan2(points[i].y - points[0].y + 0.0, points[i].x - points[0].x + 0.0); if(points[i].ang < 0) points[i].ang += 2*PI; points[i].sqrDist = (points[i].y-points[0].y)*(points[i].y-points[0].y) + (points[i].x-points[0].x)*(points[i].x-points[0].x); } sort(points+1, points+dianNum, compare); int validIdx[110], valid; validIdx[0] = 1, valid = 1; double ang = points[1].ang; for(int i = 2; i < dianNum; i++){ if(abs(points[i].ang - ang) < 1e-8) continue; ang = points[i].ang; validIdx[valid] = i; valid++; } int startValidIdx = 0; for(int i = 0; i < valid-1; i++){ if(cha(points[validIdx[i]].ang, points[validIdx[i+1]].ang) > PI - 1e-8){ startValidIdx = i+1; break; } } int pxIdx[110]; for(int i = 0; i < valid; i++){ pxIdx[i] = validIdx[(i+startValidIdx)%valid]; } toubaoNum = 2; toubaoIdx[0] = pxIdx[0], toubaoIdx[1] = pxIdx[1]; for(int i = 2; i < valid; i++){ if(!neimian(points[toubaoIdx[toubaoNum-2]], points[toubaoIdx[toubaoNum-1]], points[0], points[pxIdx[i]])){ //最后一个都在外面,直接加入 toubaoIdx[toubaoNum] = pxIdx[i]; toubaoNum++; } else{ int l = 0, u = toubaoNum - 2; while(l != u){ int m = (l+u)/2; if(neimian(points[toubaoIdx[m]], points[toubaoIdx[m+1]], points[0], points[pxIdx[i]])){ u = m; } else{ l = m+1; } } toubaoIdx[l+1] = pxIdx[i]; toubaoNum = l+2; } } toubaoIdx[toubaoNum] = 0; toubaoNum++; } void kingdom::getMianji(){ area = 0; for(int i = 0; i < toubaoNum-2; i++){ area += mianji(points[toubaoIdx[i]], points[toubaoIdx[i+1]], points[toubaoIdx[toubaoNum-1]]); } } bool inside(pt &p, kingdom &k){ int z = 0, f = 0; for(int i = 0; i < k.toubaoNum; i++){ int sigh = sign(k.points[k.toubaoIdx[i]], k.points[k.toubaoIdx[(i+1)%k.toubaoNum]], p); if(sigh > 0) z++; if(sigh < 0) f++; if(z > 0 && f > 0) return 0; } return 1; } int main() { int gs = 0; for(int i = 0; i < 25 && kd[i].getData(); i++){gs++;} bool hong[25] = {0}; for(int i = 0; i < gs; i++){ kd[i].getToubao(); kd[i].getMianji(); } int msx, msy; double ans = 0; while(scanf("%d%d", &msx, &msy) > 0){ if(msx == -1 && msy == -1) break; pt temp; temp.x = msx, temp.y = msy; for(int i = 0; i < gs; i++){ if(inside(temp, kd[i])){ if(!hong[i]){ hong[i] = 1; ans += kd[i].area; } break; } } } printf("%.2lf\n", ans); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator