| ||||||||||
| 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