Submission #1196220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196220		vnedu	별자리 2 (JOI14_constellation2)	C++17	15 / 100	44 ms	328 KiB

constellation2

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }

#define fi first
#define se second

#define pb push_back
#define ii pair<int, int>

#define all(x) x.begin(), x.end()

#define TASK "nonsense"

/// end of template ///

const int N = 3e3 + 10;
struct Vecto
{
    ll x,y;
    Vecto() {}
    Vecto(ll x, ll y) : x(x),y(y) {}
};
ll crossProduct(Vecto u, Vecto v)
{
    return u.x*v.y-u.y*v.x;
}
int sign(ll x)
{
    if(x>0) return 1;
    if(x<0) return -1;
    return 0;
}
struct Point
{
    ll x,y;
    Point() {}
    Point(ll x, ll y) : x(x),y(y) {}
    Vecto operator - (const Point &S) const
    {
        return Vecto(x-S.x,y-S.y);
    }
} point[N];
struct Triangle
{
    Point a[3];
    Triangle() {}
    Triangle(Point A, Point B, Point C) : a{A,B,C} {}
};
bool segmentIntersect(Point A, Point B, Point C, Point D)
{
    ll ABxAC=crossProduct(B-A,C-A);
    ll ABxAD=crossProduct(B-A,D-A);
    ll CDxCA=crossProduct(D-C,A-C);
    ll CDxCB=crossProduct(D-C,B-C);
    if(ABxAC==0 || ABxAD==0 || CDxCA==0 || CDxCB==0)
    {
        if(ABxAC==0 && sign(crossProduct(A-C,B-C))<=0) return 1;
        if(ABxAD==0 && sign(crossProduct(A-D,B-D))<=0) return 1;
        if(CDxCA==0 && sign(crossProduct(C-A,D-A))<=0) return 1;
        if(CDxCB==0 && sign(crossProduct(C-B,D-B))<=0) return 1;
        return 0;
    }
    return (sign(ABxAC)*sign(ABxAD)==-1 && sign(CDxCA)*sign(CDxCB)==-1);
}
bool insideTritangle(Triangle A, Point p)
{
    int o[3];
    bool hasNeg=0,hasPos=0;
    for(int i=0;i<3;++i)
    {
        o[i]=sign(crossProduct(A.a[(i+1)%3]-A.a[i],p-A.a[i]));
        hasNeg|=(o[i]<0);
        hasPos|=(o[i]>0);
    }
    return !(hasNeg && hasPos);
}
bool triangleIntersect(Triangle A, Triangle B)
{
    for(int i=0;i<3;++i) for(int j=0;j<3;++j)
    {
        if(segmentIntersect(A.a[i],A.a[(i+1)%3],B.a[j],B.a[(j+1)%3])) return 1;
    }
    for(int i=0;i<3;++i) if(insideTritangle(B,A.a[i])) return 1;
    for(int j=0;j<3;++j) if(insideTritangle(A,B.a[j])) return 1;
    return 0;
}

int n,c[N];

namespace sub1
{
    bool check()
    {
        return (n<=30);
    }
    void solve()
    {
        int ans=0;
        for(int i1=1;i1<=n;++i1) for(int j1=i1+1;j1<=n;++j1) for(int k1=j1+1;k1<=n;++k1)
        for(int i2=i1+1;i2<=n;++i2) for(int j2=i2+1;j2<=n;++j2) for(int k2=j2+1;k2<=n;++k2)
        {
            if(i2!=j1 && i2!=k1 && j2!=j1 && j2!=k1 && k2!=j1 && k2!=k1 && c[i1]!=c[j1] && c[i1]!=c[k1] && c[j1]!=c[k1] && c[i2]!=c[j2] && c[i2]!=c[k2] && c[j2]!=c[k2])
            {
    //            cout<<i1<<' '<<j1<<' '<<k1<<'\n';
    //            cout<<i2<<' '<<j2<<' '<<k2<<'\n';
    //            cout<<'\n';
                Triangle A=Triangle(point[i1],point[j1],point[k1]);
                Triangle B=Triangle(point[i2],point[j2],point[k2]);
                ans+=!triangleIntersect(A,B);
            }
        }
        cout<<ans;
    }
}
void solve()
{
    cin>>n;
    for(int i=1;i<=n;++i) cin>>point[i].x>>point[i].y>>c[i];
    if(sub1::check()) return void(sub1::solve());
}
int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

//    freopen(TASK".inp","r",stdin);
//    freopen(TASK".out","w",stdout);

    int testcase=1;
//    cin>>testcase;

    while (testcase--)
        solve();

    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 0 / 40
• Subtask 3: 0 / 45