大致题意:

  给出一个凸包,以及凸包内的两个点p1,p2,求有多少条经过凸包顶点的直线能够将凸包分割为两部分,且给出的两点分别属于不同的部分

  

  枚举凸包的顶点,二分求出p1,p2线段左边的最大坐标L以及右边的最小坐标R,则答案为R-L-1的累加和除以2

  注意文件输入,输出

   

 #include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<time.h>
#include<cstdlib>
#include<cmath>
#include<list>
using namespace std;
#define MAXN 100100
#define eps 1e-9
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Fore(i,a,b) for(int i=a;i>=b;i--)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define mkp make_pair
#define pb push_back
#define cr clear()
#define sz size()
#define met(a,b) memset(a,b,sizeof(a))
#define iossy ios::sync_with_stdio(false)
#define fre freopen
#define pi acos(-1.0)
#define inf 1e6+7
#define Vector Point
const int Mod=1e9+;
typedef unsigned long long ull;
typedef long long ll;
int dcmp(double x){
if(fabs(x)<=eps) return ;
return x<?-:;
}
struct Point{
double x,y;
int id;
Point(double x=,double y=):x(x),y(y) {}
bool operator < (const Point &a)const{
if(x==a.x) return y<a.y;
return x<a.x;
}
Point operator - (const Point &a)const{
return Point(x-a.x,y-a.y);
}
Point operator + (const Point &a)const{
return Point(x+a.x,y+a.y);
}
Point operator * (const double &a)const{
return Point(x*a,y*a);
}
Point operator / (const double &a)const{
return Point(x/a,y/a);
}
void read(){
scanf("%lf%lf",&x,&y);
}
void out(){
cout<<"debug: "<<x<<" "<<y<<endl;
}
bool operator == (const Point &a)const{
return dcmp(x-a.x)== && dcmp(y-a.y)==;
}
};
double Dot(Vector a,Vector b) {
return a.x*b.x+a.y*b.y;
}
double dis(Vector a) {
return sqrt(Dot(a,a));
}
double Cross(Point a,Point b){
return a.x*b.y-a.y*b.x;
}
int n;
Point p[];
int ls,rs;
int chk1(Point p1,Point p2,int pos){
int l=pos+,r=pos+n-;
while(l<r){
int mid=l+r>>;
if(dcmp(Cross(p[mid]-p[pos],p1-p[pos]))<= && dcmp(Cross(p[mid]-p[pos],p2-p[pos])<=)) r=mid;
else l=mid+;
}
return l;
}
int chk2(Point p1,Point p2,int pos){
int l=pos+,r=pos-+n;
while(l<r){
int mid=l+r+>>;
if(dcmp(Cross(p[mid]-p[pos],p1-p[pos]))>= && dcmp(Cross(p[mid]-p[pos],p2-p[pos]))>=) l=mid;
else r=mid-;
}
return l;
}
Point p1,p2;
void solve(){
For(i,,n) p[i].read();
p1.read();p2.read();
ll ans=;
For(i,,n) p[i+n]=p[i];
For(i,,n){
ls=chk1(p1,p2,i);
rs=chk2(p1,p2,i);
if(ls!=rs)ans+=abs(ls-rs)-;
}
cout<<ans/<<endl;
}
int main(){
// fre("in.txt","r",stdin);
freopen("kingdom.in","r",stdin);
freopen("kingdom.out","w",stdout);
int t=;
while(~scanf("%d",&n) &&n) solve();
return ;
}

最新文章

  1. java线程 - 多线程 - 守护线程
  2. python基于Django框架编译报错“django.core.exceptions.ImproperlyConfigured”的解决办法?
  3. python中%和format
  4. js页面跳转整理(转载未整理)
  5. ASP.NET MVC 5 入门教程 (3) 路由route
  6. ASP.NET中的常用快捷键
  7. 开源布局控件 WeifenLuo.WinFormsUI.Docking.dll使用
  8. 自定义异常以及runtime类
  9. SQLite 入门教程(二)创建、修改、删除表 (转)
  10. [TypeScript] Generating Definition Files
  11. Gprinter Android SDK V2.1.4 使用说明
  12. js编写验证码
  13. 解决Android Activity切换时出现白屏问题
  14. 利用Winscp,Putty实现Windows下编写Linux程序
  15. Bash的作业控制
  16. NOI 2008 假面舞会
  17. 解决iar试调时程序无法进入主函数的问题
  18. 分布式事务解决方案FESCAR
  19. Java虚拟机学习笔记——JVM垃圾回收机制
  20. scala程序开发入门

热门文章

  1. tf.session.run()单函数运行和多函数运行区别
  2. Java 8 Stream 用法
  3. File System Implementation 文件系统设计实现
  4. CentOS部署.NetCore服务
  5. GridControl详解(六)样式设置
  6. GridControl详解(一)原汁原味的表格展示
  7. [csp-201809-3]元素选择器-编译原理
  8. HDU 2082 找单词 (普通母函数)
  9. JSON.parse()——json字符串转JS
  10. vsftpd 安装配置详细教程