大致题意:
求多边形的最大内接三角形
旋转卡壳 模板题
- #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+7;
- typedef unsigned long long ull;
- typedef long long ll;
- int dcmp(double x){
- if(fabs(x)<=eps) return 0;
- return x<0?-1:1;
- }
- struct Point{
- double x,y;
- Point(double x=0,double y=0):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)==0 && dcmp(y-a.y)==0;
- }
- };
- 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 ConvexHull(Point *p,int n,Point *ch){
- int m=0;
- For(i,0,n-1) {
- while(m>1 && Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
- ch[m++]=p[i];
- }
- int k=m;
- Fore(i,n-2,0){
- while(m>k && Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
- ch[m++]=p[i];
- }
- if(n>1) m--;
- return m;
- }
- void Swap(int &p1,int &p2){
- p1^=p2;
- p2^=p1;
- p1^=p2;
- }
- double getAns(Point *ch,int n) {
- double ans=0;
- For(i,0,n-1){
- int j=(i+1)%n;
- int k=(j+1)%n;
- while(j!=k && k!=i){
- while(Cross(ch[j]-ch[i],ch[(k+1)%n]-ch[i])>=Cross(ch[j]-ch[i],ch[k]-ch[i])) k=(k+1)%n;
- ans=max(ans,Cross(ch[j]-ch[i],ch[k]-ch[i]));
- j=(j+1)%n;
- }
- }
- return ans;
- }
- int n,m;
- Point p[1000005];
- Point ch[1000005];
- void solve(){
- For(i,0,n-1) p[i].read();
- sort(p,p+n);
- int m=ConvexHull(p,n,ch);
- printf("%.2lf\n",getAns(ch,m)/2);
- }
- int main(){
- // fre("in.txt","r",stdin);
- int t=0;
- while(~scanf("%d",&n)) solve();
- return 0;
- }
- View Code
[hdu3934] 凸包 旋转卡壳
来源: http://www.bubuko.com/infodetail-2688066.html