Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

竟!然!1!A!附代妈&思路!

Posted by KatrineYang at 2016-09-03 12:52:56 on Problem 1264 and last updated at 2016-09-03 12:59:17
首先当然是对每个国家求头包,先找到這個国家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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator