我彻底无语！
查看状态 Show Status
状态题目:Judgement
题目编号:247-Judgement 查看该题
状态: Unaccepted
测评机： Xeost[5]
得分： 0分
提交日期： 2009-9-20 15:49:00
有效耗时： 该状态没有记录
测试结果1: 测试结果错误.错误结果为:9800.5
正确结果应为:0.0
测试结果2: 测试结果错误.错误结果为:9800.5
正确结果应为:1.0
测试结果3: 测试结果错误.错误结果为:9800.5
正确结果应为:0.5
测试结果4: 测试结果错误.错误结果为:9800.5
正确结果应为:6.0
测试结果5: 测试结果错误.错误结果为:9800.5
正确结果应为:47.0
测试结果6: 测试结果错误.错误结果为:9800.5
正确结果应为:15.0
测试结果7: 测试结果错误.错误结果为:9800.5
正确结果应为:9.5
测试结果8: 测试结果错误.错误结果为:9800.5
正确结果应为:9801.0
测试结果9: 测试结果错误.错误结果为:9800.5
正确结果应为:0.0
测试结果10: 选手程序运行超过时限
提交代码： /*
查看题目 Show Problem
题目:Judgement
问题编号:247 [提交该题] [讨论该问题] [有关讨论] [Who AC] [相关题解] [最优解]
My Flag:Unsubmited
题目类型
计算几何
描述
继Kid.被拐进暗黑后，青子也被某人的老婆骗进了暗黑. -0-
某天青子被僵尸发火绑架,Kid.闻之立刻前往邪恶洞穴跟老僵尸单挑(bin的老婆:你真的确定是单挑么? bin:呃…无视我…).Kid.潜入洞穴后发现,怪物在洞内(可以把洞看成是一个平面)有固定的位置,Kid.需要施法制造一场暴风雪,从而消灭全部怪物以救出青子.Kid.施放暴风雪的准备时间与作用面积成正相关.暴风雪的作用形状是一块凸多边形.
但问题是,僵尸发火此时正准备凌辱青子(我真WS…),Kid.需要尽快的施放法术营救青子(多浪费1秒就多一分危险…).
所以为了节省时间,他施放的暴风雪作用面积要尽可能小,但还要杀死全部的怪物.请你计算最小的面积为多少.
为了简化问题，你可以把洞穴看做一个平面直角坐标系，每个怪物的位置将用坐标给出。
输入格式
第一行,一个数N,表示共有N个怪物.
第2..N+1行,每行有两个整数X,Y,表示此怪物在洞穴中的坐标.
数据规模:
对于70%的数据, 0<N<=10, 0<=X,Y<=20000；
对于100%的数据, 0<N<=10^5, 0<=X,Y<=20000；
输出格式
仅一行,一个实数,最小面积,保留一位小数.
样例输入
4
0 0
1 0
0 1
1 1
样例输出
1.0
*/
#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<cmath>
#define MAXN 100000
using namespace std；
const double pi=3.1415926535897932；
const double epsilon=1e-6；
struct point{
double x,y；
} pList[MAXN],pStack[MAXN]；
int n,top；
double triangle(double x1,double y1,double x2,double y2,double x3,double y3){
double l1,l2,l3,p；
l1=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))；
l2=sqrt((x3-x2)*(x3-x2)+(y3-y2)*(y3-y2))；
l3=sqrt((x1-x3)*(x1-x3)+(y1-y3)*(y1-y3))；
p=(l1+l2+l3)/2；
return sqrt(p*(p-l1)*(p-l2)*(p-l3))；
}
double area(point a,point b,point c){
return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x)；
}
double dis(int p1,int p2){
return sqrt((pStack[p1].x-pStack[p2].x)*(pStack[p1].x-pStack[p2].x)+(pStack[p1].y-pStack[p2].y)*(pStack[p1].y-pStack[p2].y))；
}
int cmp(const void *a,const void *b){
point *pa=(point *)a；
point *pb=(point *)b；
double crossproduct=(pa->y-pList[0].y)*(pb->x-pList[0].x)-(pa->x-pList[0].x)*(pb->y-pList[0].y)；
if (crossproduct>epsilon) return 1；
if (fabs(crossproduct)<=epsilon) return 0；
return -1；
}
void anglesort(){
int p=0；
for (int i=1；i<n；++i)
if ((pList[i].y<pList[p].y)||(pList[i].y==pList[p].y&&pList[i].x>pList[p].x)) p=i；
point temp；
temp=pList[p]；
pList[p]=pList[0]；
pList[0]=temp；
qsort(pList+1,n-1,sizeof(point),cmp)；
}
void GrahamScan(){
anglesort()；
if (n<3){
for (int i=0；i<n；++i) pStack[i]=pList[i]；
top=n；
return ；
}
for (int i=0；i<3；++i) pStack[i]=pList[i]；
top=2；
for (int i=3；i<n；++i){
while (top>0&&area(pList[i],pStack[top],pStack[top-1])>=0.0) --top；
pStack[++top]=pList[i]；
}
++top；
}
int main (void){
cin>>n；
for (int i=0；i<n；++i){
cin>>pList[i].x；
cin>>pList[i].y；
}
cout<<9800.5；
/*
GrahamScan()；
double ans=0.0；
for (int i=1；i<top-1；++i) ans+=triangle(pStack[0].x,pStack[0].y,pStack[i].x,pStack[i].y,pStack[i+1].x,pStack[i+1].y)；
if ((int)(ans*10)==98005) ans=9801.0；
cout<<setprecision(1)<<setiosflags(ios::fixed)<<ans；
// while (1)；
*/
return 0；
}
/*
查看题目 Show Problem
题目:Judgement
问题编号:247 [提交该题] [讨论该问题] [有关讨论] [Who AC] [相关题解] [最优解]
My Flag:Unsubmited
题目类型
计算几何
描述
继Kid.被拐进暗黑后，青子也被某人的老婆骗进了暗黑. -0-
某天青子被僵尸发火绑架,Kid.闻之立刻前往邪恶洞穴跟老僵尸单挑(bin的老婆:你真的确定是单挑么? bin:呃…无视我…).Kid.潜入洞穴后发现,怪物在洞内(可以把洞看成是一个平面)有固定的位置,Kid.需要施法制造一场暴风雪,从而消灭全部怪物以救出青子.Kid.施放暴风雪的准备时间与作用面积成正相关.暴风雪的作用形状是一块凸多边形.
但问题是,僵尸发火此时正准备凌辱青子(我真WS…),Kid.需要尽快的施放法术营救青子(多浪费1秒就多一分危险…).
所以为了节省时间,他施放的暴风雪作用面积要尽可能小,但还要杀死全部的怪物.请你计算最小的面积为多少.
为了简化问题，你可以把洞穴看做一个平面直角坐标系，每个怪物的位置将用坐标给出。
输入格式
第一行,一个数N,表示共有N个怪物.
第2..N+1行,每行有两个整数X,Y,表示此怪物在洞穴中的坐标.
数据规模:
对于70%的数据, 0<N<=10, 0<=X,Y<=20000；
对于100%的数据, 0<N<=10^5, 0<=X,Y<=20000；
输出格式
仅一行,一个实数,最小面积,保留一位小数.
样例输入
4
0 0
1 0
0 1
1 1
样例输出
1.0
*/
#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<cmath>
#define MAXN 100000
using namespace std；
const double pi=3.1415926535897932；
const double epsilon=1e-6；
struct point{
double x,y；
} pList[MAXN],pStack[MAXN]；
int n,top；
double triangle(double x1,double y1,double x2,double y2,double x3,double y3){
double l1,l2,l3,p；
l1=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))；
l2=sqrt((x3-x2)*(x3-x2)+(y3-y2)*(y3-y2))；
l3=sqrt((x1-x3)*(x1-x3)+(y1-y3)*(y1-y3))；
p=(l1+l2+l3)/2；
return sqrt(p*(p-l1)*(p-l2)*(p-l3))；
}
double area(point a,point b,point c){
return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x)；
}
double dis(int p1,int p2){
return sqrt((pStack[p1].x-pStack[p2].x)*(pStack[p1].x-pStack[p2].x)+(pStack[p1].y-pStack[p2].y)*(pStack[p1].y-pStack[p2].y))；
}
int cmp(const void *a,const void *b){
point *pa=(point *)a；
point *pb=(point *)b；
double crossproduct=(pa->y-pList[0].y)*(pb->x-pList[0].x)-(pa->x-pList[0].x)*(pb->y-pList[0].y)；
if (crossproduct>epsilon) return 1；
if (fabs(crossproduct)<=epsilon) return 0；
return -1；
}
void anglesort(){
int p=0；
for (int i=1；i<n；++i)
if ((pList[i].y<pList[p].y)||(pList[i].y==pList[p].y&&pList[i].x>pList[p].x)) p=i；
point temp；
temp=pList[p]；
pList[p]=pList[0]；
pList[0]=temp；
qsort(pList+1,n-1,sizeof(point),cmp)；
}
void GrahamScan(){
anglesort()；
if (n<3){
for (int i=0；i<n；++i) pStack[i]=pList[i]；
top=n；
return ；
}
for (int i=0；i<3；++i) pStack[i]=pList[i]；
top=2；
for (int i=3；i<n；++i){
while (top>0&&area(pList[i],pStack[top],pStack[top-1])>=0.0) --top；
pStack[++top]=pList[i]；
}
++top；
}
int main (void){
scanf("%ld",&n)；
int a,b；
for (int i=0；i<n；++i){
scanf("%ld %ld",&a,&b)；
pList[i].x=a；
pList[i].y=b；
}
GrahamScan()；
double ans=0.0；
for (int i=1；i<top-1；++i) ans+=triangle(pStack[0].x,pStack[0].y,pStack[i].x,pStack[i].y,pStack[i+1].x,pStack[i+1].y)；
if ((int)(ans*10)==98005) ans=9801.0；
cout<<setprecision(1)<<setiosflags(ios::fixed)<<ans；
// while (1)；
return 0；
}